Once there was an inventor congress, where inventors from
all over the world met in one place. The organizer of the
congress reserved exactly one hotel room for each inventor.
Each inventor, however, had its own preference regarding which
room he would like to stay in. Being a clever inventor himself,
the organizer soon found an objective way of doing the room
assignments in a fair manner: each inventor wrote two different
room numbers on a fair coin, one room number on each side.
Then, each inventor threw his coin and was assigned the room
number which was shown on the upper side of his coin. If some
room had been assigned to more than one inventor, all inventors
had to throw their coins again.
As you can imagine, this assignment process could take a
long time or even not terminate at all. It has the advantage,
however, that among all possible room assignments, one
assignment is chosen randomly according to a uniform
distribution. In order to apply this method in modern days, you
should write a program which helps the organizer.
The organizer himself needs a hotel room too. As the
organizer, he wants to have some advantage: he should be able
to rate each of the rooms (the higher the rating, the better),
and the program should tell him which two room numbers he
should write on his coin in order to maximize the expected
rating of the room he will be assigned to. The program also has
access to the choices of the other inventors before making the
proposal. It should never propose two rooms for the organizer
such that it is not possible to assign all inventors to the
rooms, if a valid assignment is possible at all.
The input starts with a single number $c$ ($1
\le c \le 200$) on one line, the number of test cases.
Each test case starts with one line containing a number
$n$ ($2 \le n \le 50\, 000$), the number of
inventors and rooms. The following $n-1$ lines contain the choices of the
$n-1$ guests (excluding
the organizer). For each inventor, there is a line containing
two numbers $a$ and
$b$ ($1 \le a < b \le n$), the two room
numbers which are selected by the inventor. The last line of
each test case consists of $n$ integers $v_1, \ldots , v_ n$ ($1 \le v_ i \le 1\, 000\, 000$), where
$v_ i$ is the organizer’s
rating for room $i$.
For each test case, print a single line containing the two
different room numbers $a$
and $b$ which should be
selected by the organizer in order to maximize the expected
rating of the room he will be assigned to. If there is more
than one optimal selection, break ties by choosing the smallest
$a$ and, for equal
$a$, the smallest
$b$. If there is no way
for the organizer to select two rooms such that an assignment
of inventors to rooms is possible, print “impossible” instead.
|Sample Input 1
||Sample Output 1
2 3 4 1
100 40 70
1 1 1 1 1