방 배정

전 세계의 발명가들이 한자리에 모이는 발명가 학회가 열렸다. 주최자는 모든 발명가에게 호텔 방을 정확히 하나씩 예약해 두었다. 그런데 발명가마다 묵고 싶은 방에 대한 선호가 달랐기 때문에, 주최자는 공정하게 방을 배정하기 위한 무작위 방법을 마련했다.

각 발명가는 서로 다른 두 방 번호를 동전의 양면에 하나씩 적는다. 그런 다음 각자 동전을 던져, 위를 향한 면에 적힌 방을 배정받는다. 만약 어떤 방이 두 명 이상에게 배정되면 모든 발명가가 동전을 다시 던진다. 모든 발명가가 서로 다른 방을 가질 때까지 이 과정을 반복한다.

이 절차는 오래 걸릴 수도 있고 영원히 끝나지 않을 수도 있지만, 한 가지 유용한 성질이 있다. 동전에 적힌 번호들과 모순되지 않는 모든 방 배정 중에서 하나를 균등한 확률로 고른다는 점이다.

주최자 자신도 방이 필요하며, 이왕이면 유리한 방을 얻고 싶다. 그는 각 방에 점수를 매길 수 있고(점수가 높을수록 좋다), 다른 모든 발명가가 이미 고른 두 방 번호를 알고 있는 상태에서 자신의 동전에 적을 서로 다른 두 방 번호를 정해야 한다. 그가 배정받을 방의 기대 점수를 최대로 만드는 두 번호를 골라라. 단, 모든 발명가를 서로 다른 방에 배정하는 것이 애초에 가능한 경우라면, 그 배정을 불가능하게 만드는 두 방을 골라서는 절대 안 된다.

첫 줄에 테스트 케이스의 수 $c$ ($1 \le c \le 200$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

각 테스트 케이스의 첫 줄에는 발명가의 수이자 방의 수인 정수 $n$ ($2 \le n \le 50000$)이 주어진다. 이어지는 $n - 1$개의 줄에는 주최자를 제외한 나머지 발명가들이 고른 동전이 주어지며, 각 줄에는 그 발명가가 고른 두 방 번호 $a$와 $b$ ($1 \le a < b \le n$)가 주어진다. 마지막 줄에는 $n$개의 정수 $v_1, \dots, v_n$ ($1 \le v_i \le 1000000$)이 주어지고, $v_i$는 주최자가 매긴 $i$번 방의 점수이다.

각 테스트 케이스마다, 주최자가 배정받을 방의 기대 점수를 최대로 만들기 위해 자신의 동전에 적어야 하는 서로 다른 두 방 번호 $a$와 $b$ ($a < b$)를 한 줄에 출력한다. 최적인 선택이 여러 개라면 $a$가 가장 작은 것을, $a$가 같다면 $b$가 가장 작은 것을 출력한다. 모든 발명가를 서로 다른 방에 배정하는 것이 가능하도록 유지하면서 두 방을 고를 방법이 전혀 없다면, 대신 impossible을 출력한다.