LoL 토너먼트

올해 LoL 토너먼트에는 참가자가 $n$명 있고, 1번부터 $n$번까지 번호가 붙어 있다. 당신은 Dota를 아주 잘하고 웃음이 많아서 참가하기로 했다.

이 대회의 진행 방식은 독특하다. 싱글 엘리미네이션이나 리그전 같은 흔한 방식 대신, 주최 측이 만든 규칙으로 우승자를 가린다.

대회는 $n-1$개의 라운드로 이루어지고, 마지막 라운드의 승자가 우승자다. 진행은 다음과 같다.

1. 1번 라운드에서는 $a_1$번 참가자와 $b_1$번 참가자가 맞붙는다. 패자는 탈락하고, 승자는 다음 라운드로 올라가면서 번호가 $n+1$번으로 바뀐다.
2. 2번 라운드에서는 $a_2$번 참가자와 $b_2$번 참가자가 맞붙고, 승자의 번호는 $n+2$번이 된다.
3. 일반적으로 $i$번 라운드에서는 $a_i$번 참가자와 $b_i$번 참가자가 맞붙고, 승자의 번호는 $n+i$번이 된다.

$n-1$개의 라운드가 모두 끝나면 참가자가 한 명만 남고, 그 번호는 $2n-1$번이다. 이 사람이 우승자다.

이 방식이 불공평하다는 것은 금방 알 수 있다. 그래도 대회 자체는 앞뒤가 맞는다. 자기가 나가는 라운드를 모두 이긴 참가자가 우승하고, 나머지 참가자는 정확히 한 명에게 한 번만 진다.

그래서 당신은 이 구조를 이용하기로 했다. 우승 확률이 가장 커지도록 1번부터 $n$번 중에서 처음 번호를 고르려고 한다. 어떤 번호를 골라야 하는가? 그런 번호가 여러 개일 수 있으니, 해당하는 번호를 모두 증가하는 순서로 출력한다.

한 라운드를 이길 확률은 상대가 누구든 $p$다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 $n$과 $p$가 공백으로 구분되어 주어진다. 이어지는 $n-1$개의 줄은 대진을 나타낸다. 그중 $i$번째 줄에는 두 정수 $a_i$와 $b_i$가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 5$
• $1 \le n \le 10^5$
• 리스트 $[a_1, a_2, \dots, a_{n-1}, b_1, b_2, \dots, b_{n-1}]$에는 중복이 없다.
• $1 \le a_i, b_i < n+i$
• $0 \le p \le 1$
• $p$는 소수점 아래 7자리로 주어진다.

각 테스트 케이스마다 한 줄에, 우승 확률을 최대로 만드는 처음 번호를 증가하는 순서로 공백 하나씩으로 구분해 출력한다.