The Best Path

Time Limit: 9000/3000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

Description

Alice is planning her travel route in a beautiful valley. In this valley, there are $N$ lakes, and $M$ rivers linking these lakes. Alice wants to start her trip from one lake, and enjoys the landscape by boat. That means she need to set up a path which go through every river exactly once. In addition, Alice has a specific number ($a_1, a_2, ... , a_n$) for each lake. If the path she finds is $P_0 \rightarrow P_1 \rightarrow ... \rightarrow P_t$, the lucky number of this trip would be $a_{P_0} \quad XOR \quad a_{P_1} \quad XOR \quad... \quad XOR \quad a_{P_t}$. She want to make this number as large as possible. Can you help her?

Input

The first line of input contains an integer $t$, the number of test cases. $t$ test cases follow.

For each test case, in the first line there are two positive integers $N~(N \leq 100000)$ and $M~(M \leq 500000)$, as described above. The $i$-th line of the next $N$ lines contains an integer $a_i(\forall i, 0 \leq a_i \leq 10000)$ representing the number of the $i$-th lake.

The $i$-th line of the next $M$ lines contains two integers $u_i$ and $v_i$ representing the $i$-th river between the $u_i$-th lake and $v_i$-th lake. It is possible that $u_i=v_i$.

Output

For each test cases, output the largest lucky number. If it dose not have any path, output "Impossible".

Sample Input

2 3 2 3 4 5 1 2 2 3 4 3 1 2 3 4 1 2 2 3 2 4

Sample Output

2 Impossible

Hint

wange2014

Source

2016 ACM/ICPC Asia Regional Qingdao Online

提交代码