• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

Middle out is a compression algorithm invented by PiedPiper (a compression company) during D2F calculations about how fast two agents can manipulate data with help of a third agent. Third agent is in the middle, while the other two are on two endpoints of a stream. Third agent can stay in middle if and only if it holds the D2FB (D2F Bridge) condition. D2FB condition is achieved if and only if D2DA (angle between D2Fs of agents) is smaller than D2DAT (D2DA threshold).

PiedPiper CEO just got fired and he was the only one who knew how to calculate the best D2DAT, but since Erlich(one of PiedPiper’s board members) is the one who came up with the D2F idea, he knows about some parts of the algorithm to calculate the best D2DAT. Your job is to calculate the minimum integer value for D2DAT such that D2DB condition holds between all agents of the compression process.

Describing what D2F and D2FB are, is kinda hard, so we’re gonna use a simplified version to show you how the algorithm works. You can suppose D2F is a tall wall, D2FB is a bridge connecting two walls to each other and D2DA is height difference between two D2Fs.

Minimum possible value for D2DAT is the maximum D2DA between all connected agents.

ورودی

The first line of input shows the number of test cases $T$. $$1 \leq T \leq 30$$

Each test case starts with an integer $N$ indicating number of agents and is followed by $N+1$ lines. Next line contains $N$ space separated integers $D2F_1, D2F_2, \dots, D2F_N$ for agents. Line $i+2$’th of the test case describes connected agents to $i$’th agent. $$1 \leq N \leq 100, \quad \quad 1 \leq D2F_i \leq 10,000$$

each line starts with an integer $M$ and is followed by $M$ space separated integers $a_1, a_2, \dots, a_m,,$. $a_j$ means that agent $i$ and agent $j$ are connected to each other. $$ 0 \leq M \leq N, \quad \quad 1 \leq a_j \leq M$$

خروجی

For each test case, print the minimum D2DAT in a line.

مثال‌ها

ورودی نمونه ۱

2
2
5 7
1 2
1 1
4
2 5 8 9
2 2 3
3 1 4 3
2 2 1
1 2

خروجی نمونه ۱

2
6

In the first test case:

Agent one D2F has height of 5 and agent two D2F has height of 7. Difference between them is 2 So the answer is 2.

in the second test case:

Agent one D2F has height of 2, agent two has height of 5, agent tree has height of 8 and agent four has height of 9.

• Difference between agents one and two is 3
• Difference between agents one and three is 6
• Difference between agents two and four is 4
• Difference between agents two and three is 3

So the answer is 6.