Это интерактивная задача.

После завершения ремонта электросети голографический проектор наконец успешно запустился. С наступлением ночи голограммы в небе стали яркими и красочными. После завершения всех приготовлений, Сяо Т и Сяо С официально открыли ночную программу, пригласив всех желающих принять участие в тщательно подготовленной игре на проверку взаимопонимания — «Расшифровка потока света».

Лучи света в центре площади переплетаются, медленно собираясь в дерево из света. Световое дерево состоит из нескольких светящихся узлов и соединяющих их световых линий, образуя структуру дерева. В начале игры все линии не подсвечены, и участники не могут наблюдать ни одной линии. Karuha, управляющая системой, первой показывает участнику, стоящему у консоли, секретное число. Затем световые линии начинают загораться одна за другой, и участник должен в момент появления каждой линии определить направление её потока; а напарник, стоящий на другом конце сцены, должен, основываясь лишь на итоговой структуре ориентированного дерева, точно угадать это секретное число.

Как участники праздника, Neri и Noir решили объединить усилия, чтобы пройти это испытание.

В этом испытании Neri будет стоять у консоли. Karuha сначала даст ей два целых числа $n, s$ ($1 \le s \le 2^{n-1}$), которые обозначают количество световых узлов в дереве и секретное число соответственно.

Затем Karuha будет по очереди подсвечивать $n - 1$ световых линий, и Neri должна в момент появления каждой линии немедленно указать направление её потока.

Что касается Noir, стоящей на другом конце сцены, она будет наблюдать итоговую форму светового дерева, заполненного потоками света. Ей нужно, основываясь на направлениях потоков этих линий, угадать секретное число $s$, переданное Karuha для Neri.

Чтобы выиграть в этой игре, Neri и Noir должны заранее разработать стратегию, чтобы гарантированно пройти это испытание на взаимопонимание.

Ваша программа будет запущена дважды: в первый раз она будет играть роль Neri, определяя направление потока каждой линии, а во второй раз — роль Noir, угадывая секретное число по итоговой форме светового дерева. Интерактор будет играть роль Karuha, передавая информацию вашей программе.

В первом запуске ваша программа сначала получит количество световых узлов $n$ и секретное число $s$, а затем по очереди получит $n - 1$ подсвечиваемую световых линию. Ваша программа должна немедленно вывести в интерактор направление потока для каждой линии, чтобы передать информацию для второго запуска.

Во втором запуске ваша программа получит от интерактора информацию, переданную из первого запуска, то есть направления потоков световых линий на дереве, а затем должна, основываясь на этой информации, угадать секретное число $s$, переданное Karuha для Neri.

Входные данные

Каждый тест содержит несколько наборов данных. Первая строка ввода содержит два целых числа $T, r$ ($1 \le T \le 10^4, r \in \{1, 2\}$), обозначающих количество наборов данных и номер этапа. Для каждого набора данных:

• Если $r = 1$:

  • В первой строке вводятся два целых числа $n, s$ ($3 \le n \le 30, 1 \le s \le 2^{n-1}$), обозначающих количество световых узлов в дереве и секретное число.
  • Далее по очереди будут подсвечиваться $n - 1$ световых линий. При появлении каждой линии вводятся два целых числа $u, v$ ($1 \le u < v \le n$), обозначающих номера двух узлов, соединенных линией. Вы должны немедленно вывести строку с двумя целыми числами $u, v$ или $v, u$, обозначающими направление потока от $u$ к $v$ или от $v$ к $u$.
  • Примечание:
    • Для каждой световой линии вы обязаны вывести направление потока и сбросить буфер стандартного вывода, прежде чем сможете продолжить ввод следующей подсвечиваемой линии.

• Если $r = 2$:

  • В первой строке вводится целое число $n$ ($3 \le n \le 30$), обозначающее количество световых узлов в дереве.
  • Далее следуют $n - 1$ строк, в каждой из которых вводятся два целых числа $u, v$ ($1 \le u, v \le n$), обозначающие световой поток от узла $u$ к узлу $v$.
  • Вы должны немедленно вывести одну строку с целым числом, обозначающим угаданное секретное число $s$.
  • Примечание:
    • Порядок ввода тестов внутри одного теста может отличаться от порядка в первом запуске.
    • Для одного и того же набора данных порядок ввода световых линий в двух запусках может отличаться, но номера узлов остаются неизменными.
    • Для каждого набора данных вы обязаны вывести угаданное число $s$ и сбросить буфер стандартного вывода, прежде чем сможете продолжить ввод следующего набора данных.

Примеры

Входные данные 1

1 2
7 21
3 16
4 3 5
5 2 4
6 3 4
7 1 2
8 6 7
9 9 59
10 1 2
11 1 4
12 3 4
13 3 5
14 3 8
15 5 6
16 6 7
17 8 9

Выходные данные 1

6 1
3 5
4 2
3 4
1 2
7 6

Примечание

Рис. 1: Первый набор данных

Рис. 2: Второй набор данных

Входные данные 2

2 2
9
9 8
1 2
5 6
6 7
1 4
3 5
8 3
3 4
7
1 2
4 2
6 1
3 5
3 4
7 6

Выходные данные 2

59
21