C :: Bahman's Network

Time Limit: 5 Seconds    Memory Limit: 65536 KB

In country of Utopia, Bahman has recently accepted the important task of constructing the nation’s first network infrastructure. After months of research and analysis, he has realized that people will use their personal computers to connect to this network. Clients will have network connectivity as soon as they establish a link with one of the routers in the network. This initial router will be used to introduce their messages, i.e. packets will be first transmitted to this router (from client’s machine) and from there will travel through series of intermediary routers to reach their destination. For destinations out of Utopia, messages should be first routed to certain boundary routers. These routers are directly connected to internet so they are capable of forwarding incoming packets to the global network. The example below depicts a network based on Bahman’s design:

In this so-called network, each message has an attribute called TTL which holds maximum number of intermediary routers that message is allowed to go through. Messages will be created with an initial TTL value of 65535. Additionally, each router is assigned a TTL limit used to restrict the traffic passing through. Upon arriving at each router, message TTL value will be reduced by 1 and then the minimum of the new TTL value and the router’s TTL limit will be assigned to the message. For example, consider a message M1 with TTL value 65535 and a router R1 with TTL limit 100. Upon arrival at R1, M1’s TTL value will be updated to 100 (minimum of 65534 and 100).

Bahman has little knowledge of rules governing the global network infrastructures, so to be on the safe side, he is expecting all outgoing messages to have the maximum possible TTL as they reach one of the boundary routers. Finally, he wants to know the minimum TTL value of messages reaching the network boundaries. In case a particular message can not reach the boundary, it’s TTL value will be considered 0 in our calculations.

No computer can be connected to the boundary routers.

Input

The input contains several test cases.
In the first line of input comes T (0 < T ≤ 100), the number of test cases.
For each test case, two positive integers N and M are provided which denote the number of routers and links respectively (1 ≤ N ≤ 500 and 1 ≤ M ≤ 3000). On the next line, N space-separated TTL values will be provided.
Next, we will have n lines each describing a router by first providing the number of adjacent routers and then providing their identifiers. Note that routers are assigned 1...N as their identifiers. Finally, on the last line of input a parameter k denoting the number of boundary routers and k space-separated identifiers are given.

Output

For each test case, print out the minimum value of messages as they reach network boundaries.

Sample Input

3
2 1
100 100
1 2
1 1
1 2
4 4
100 5 10 5
2 2 3
2 1 3
3 1 2 4
1 3
2 2 4
3 1
100 100 100
1 2
1 1
0
1 3

Sample Output

99
5
0
Submit

Source: 12th Iran Nationwide Internet Contest - Final