Colorful Village

Colorful Village는 인기 있는 관광지이다. 이 마을에는 1번부터 2n번까지 번호가 붙은 집이 2n채 있다. 각 집은 1번부터 n번까지 번호가 붙은 n가지 색 중 하나로 칠해져 있다. 각 색은 정확히 두 집에 칠해져 있다.

Colorful Village에는 2n-1개의 양방향 도로가 있다. 각 도로는 서로 다른 두 집을 잇고, 이 도로들을 따라 어느 집에서든 다른 모든 집으로 갈 수 있다.

Catherine이 Colorful Village를 여행하려고 한다. 시간이 부족해서 색마다 정확히 한 집씩, 총 n채의 집으로 이루어진 집합 S를 방문하려고 한다. 집 사이를 이동해야 하므로 이 집합은 연결되어 있어야 한다. 즉, S에 속한 임의의 집에서 S에 속한 다른 임의의 집으로 도로를 따라 갈 수 있어야 하며, 이동 중에는 S에 속한 집만 지나야 한다.

Catherine을 도와 색마다 한 집씩 골라 연결된 집합 S를 n채 찾거나, 그러한 S가 없다고 보고하자.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^5$)가 주어진다. 이어서 테스트 케이스들이 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$ ($1 \le n \le 10^5$) 하나가 주어진다.

둘째 줄에는 $2n$개의 정수 $c_1, c_2, \ldots, c_{2n}$이 주어진다. 이는 각 집의 색이다 ($1 \le c_i \le n$). 이 줄에서 $1$부터 $n$까지의 모든 정수는 정확히 두 번씩 나타난다.

이어지는 $2n-1$개의 줄 중 $i$번째 줄에는 $i$번째 도로가 잇는 두 집 $u_i$와 $v_i$가 주어진다 ($1 \le u_i, v_i \le 2n$; $u_i \ne v_i$).

모든 테스트 케이스의 $n$의 합은 $10^5$을 넘지 않는다는 것이 보장된다.

각 테스트 케이스에 대해, 조건을 만족하는 집합이 존재하지 않으면 정수 $-1$ 하나를 출력한다.

그렇지 않으면 순서와 상관없이 서로 다른 정수 $n$개 $s_1, s_2, \ldots, s_n$을 출력한다. 이들은 색마다 한 집씩 골라 만든 연결된 집합 S의 집 번호이다 ($1 \le s_i \le 2n$). 답이 여러 개이면 그중 아무것이나 출력해도 된다.