這是一道通信題。

請務必在每次輸出後刷新標準輸出緩衝區。各程式語言的刷新方式如下：

• 對於 C/C++，請使用 fflush(stdout) 或 cout.flush()；
• 對於 Java，請使用 System.out.flush()；
• 對於 Python，請使用 sys.stdout.flush()。

供電網絡修復完畢，全息投影儀終於順利啟動。隨著夜色漸深，半空中的全息投影愈發繽紛絢麗。一切就緒後，小 T 和小 S 正式拉開了夜間活動的帷幕，邀請大家結伴，共同參與這場精心籌備、考驗雙人合作默契的光影遊戲「流光解密」。

廣場中央的光束交織在一起，緩緩匯聚成一棵全息光樹。光樹由若干個懸浮的光團作為結點與連接它們的流光線路組成，呈現出純粹的樹形結構。遊戲開始時，所有線路均未點亮，挑戰者無法觀測到任何點亮的線路。執行系統操作的 Karuha 會率先向駐守在控制台前的一名挑戰者揭示一個神秘數字。隨後，各流光線路會逐一亮起，該挑戰者必須在每條線路浮現的瞬間，決定其流動的方向；而站在舞台另一端的搭檔，則需僅憑最終形成的定向樹結構，準確推斷出這個神秘數字。

作為慶典參與者，Neri 和 Noir 決定配合完成這項挑戰。

在這項挑戰中，Neri 將駐守在控制台前。系統的 Karuha 首先會向她給出兩個正整數 $n, s$ ($1 \le s \le 2^{n-1}$)，分別表示全息光樹包含的光團數量與神秘數字。

隨後，Karuha 將依次點亮 $n - 1$ 條流光線路，Neri 必須在每條線路亮起時，立即為其指定流動的方向。

對於站在主舞台另一端的 Noir，她將觀察到整棵全息光樹充滿流光的最終形態。她需要根據這些線路的流動方向，推斷出 Karuha 傳遞給 Neri 的神秘數字 $s$。

為了贏得這場光影挑戰，Neri 和 Noir 需要提前制定一套策略，以確保在這個考驗雙人默契的遊戲中順利通關。

實作細節

你的程式將會獨立運行兩次，其中第一次將扮演 Neri 決定每條線路流動的方向，第二次將扮演 Noir 根據全息光樹的最終形態推斷出神秘數字。交互器將扮演 Karuha，向你的程式傳遞信息。

在第一次運行中，你的程式會首先收到全息光樹包含的光團數量 $n$ 與神秘數字 $s$，然後依次收到 $n - 1$ 條點亮的流光線路。你的程式需要立即向交互庫輸出為其指定的流動方向，從而向第二次運行傳遞信息。

在第二次運行中，你的程式會從交互器收到來自第一次運行的信息，即全息光樹上流光線路的流動方向，然後需要根據這些信息推斷出 Karuha 傳遞給 Neri 的神秘數字 $s$。

輸入輸出格式

每個測試點中包含多組測試數據。輸入的第一行包含兩個正整數 $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
2 7 21
3 1 6
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
1 4
3 4
3 5
8 3
5 6
6 7
9 8

說明

兩組測試數據的所有流光線路定向後，全息光樹的形態分別如下：

圖 1: 第一組測試數據

圖 2: 第二組測試數據

輸入格式 2

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

輸出格式 2

59
21

測試程序方式

下發的腳本文件 treedir_testing_tool.py 可以協助你進行本地測試以驗證程序的正確性，並打印詳細的交互過程。測試時，請將該腳本與你編譯生成的可執行文件置於同一目錄下，隨後在終端內運行以下命令：

python3 treedir_testing_tool.py [--quiet] <data_file> <program> <arguments>

其中：

• -q, --quiet 為可選參數，使用該參數後，測試腳本將不再打印詳細的交互過程。
• data_file 為提供給測試腳本的輸入文件路徑。該文件需滿足以下格式：
  • 第一行包含兩個非負整數 $T, seed$，分別代表測試組數，與用於打亂測試順序及樹內連邊順序的隨機數種子。若指定 $seed = 0$，則表示不進行打亂。
  • 每組數據的格式與前述的「第一次運行」的輸入格式完全相同。
• program 為你編譯生成的可執行文件路徑。
• arguments 為傳遞給該可執行文件的額外命令行參數。

關於測試腳本的更多實現細節，請直接查閱其原始碼。

注意：

1. 測試腳本與實際評測時的交互庫實現不完全相同，本地測試結果不具終止性，僅供調試階段參考；

2. 測試腳本僅會對 data_file 中的數據進行基礎的格式校驗，不會檢查其是否合法地滿足了題目限制（例如，不會檢查 $s$ 是否滿足 $1 \le s \le 2^{n-1}$ 的限制，也不會判斷所有流光線路能否正確構成一棵樹）；

3. 測試腳本不會監控程序的空間與時間消耗，無法用於測試是否符合題目的空間限制。