LoL Tournament

There are $n$ contestants in this year's LoL tournament, numbered from 1 to $n$. You decided to join, since you are very good at Dota and you laugh a lot.

The format of this tournament is unusual. Instead of single elimination, round robin or another common format, the organizers use their own rule for deciding the winner.

The tournament has $n-1$ rounds, and the winner of the last round is the champion. It goes like this.

1. In round 1, the contestants numbered $a_1$ and $b_1$ compete. The loser is eliminated, and the winner advances and is renumbered $n+1$.
2. In round 2, the contestants numbered $a_2$ and $b_2$ compete, and the winner is renumbered $n+2$.
3. In general, in round $i$ the contestants numbered $a_i$ and $b_i$ compete, and the winner is renumbered $n+i$.

After all $n-1$ rounds only one contestant is left, numbered $2n-1$. That contestant wins the tournament.

It is not hard to see that this format is unfair. Even so, the contest is well formed: a contestant wins by winning every round he or she plays, and everyone else loses to exactly one other contestant.

You decided to work the system. You want to choose your initial number, between 1 and $n$, so that your probability of winning the tournament is as large as possible. Which number should you take? There can be several such numbers, so print all of them in increasing order.

Your probability of winning a single round is $p$, whoever the opponent is.

The first line contains $T$, the number of test cases.

The first line of each test case contains $n$ and $p$ separated by a space. The next $n-1$ lines describe the tournament. The $i$-th of those lines contains two integers $a_i$ and $b_i$ separated by a space.

Constraints

• $1 \le T \le 5$
• $1 \le n \le 10^5$
• The list $[a_1, a_2, \dots, a_{n-1}, b_1, b_2, \dots, b_{n-1}]$ contains no duplicates.
• $1 \le a_i, b_i < n+i$
• $0 \le p \le 1$
• $p$ is written with 7 digits after the decimal point.

For each test case, print one line with the initial numbers that maximize your probability of winning, in increasing order, separated by single spaces.