Room Assignments

At an inventors' convention, inventors from all over the world gather in one place. The organizer has reserved exactly one hotel room for every inventor. Each inventor, however, has a preference about which room to stay in, so the organizer settled on a fair, random way of assigning rooms.

Every inventor writes two different room numbers on a coin, one on each side. Each inventor then tosses the coin and is assigned the room number that lands face up. If any room ends up assigned to more than one inventor, all inventors toss their coins again. This repeats until every inventor holds a distinct room.

This procedure may take a long time, and might even never terminate, but it has one useful property: among all room assignments that are consistent with the coins, it selects one uniformly at random.

The organizer needs a room too, and wants an advantage. He can rate every room (a higher rating is better), and, knowing the two room numbers already chosen by each of the other inventors, he must decide which two different room numbers to write on his own coin. Choose the two numbers that maximize the expected rating of the room he ends up assigned to. He must never pick two rooms that make it impossible to assign every inventor to a distinct room, whenever such an assignment is possible at all.

The first line contains an integer $c$ ($1 \le c \le 200$), the number of test cases. Each test case is given as follows.

The first line of a test case contains an integer $n$ ($2 \le n \le 50000$), the number of inventors, which equals the number of rooms. The next $n - 1$ lines describe the coins of the other inventors (everyone except the organizer); each such line contains two integers $a$ and $b$ ($1 \le a < b \le n$), the two room numbers that inventor chose. The last line contains $n$ integers $v_1, \dots, v_n$ ($1 \le v_i \le 1000000$), where $v_i$ is the organizer's rating of room $i$.

For each test case, print a single line with the two different room numbers $a$ and $b$ ($a < b$) the organizer should write on his coin to maximize the expected rating of his assigned room. If several choices are optimal, output the one with the smallest $a$, breaking further ties by the smallest $b$. If the organizer cannot pick any two rooms that keep a valid assignment of all inventors to distinct rooms possible, print impossible instead.