これは通信問題です。

各出力の後に標準出力バッファを必ずフラッシュしてください。各プログラミング言語におけるフラッシュ方法は以下の通りです。

• 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は事前に戦略を立て、この二人の阿吽の呼吸を試すゲームを確実にクリアする必要があります。

実装の詳細

あなたのプログラムは独立して2回実行されます。1回目はNeriとして各ラインの流れる方向を決定し、2回目はNoirとして全光樹の最終形態から神秘的な数字を推測します。インタラクタがKaruhaを演じ、あなたのプログラムに情報を伝達します。

1回目の実行では、あなたのプログラムはまず全光樹に含まれる光の塊の数 $n$ と神秘的な数字 $s$ を受け取り、続いて順番に $n - 1$ 本の点灯する光のラインを受け取ります。あなたのプログラムは直ちに、指定した流れる方向をインタラクタに出力しなければなりません。これにより、2回目の実行へ情報を伝達します。

2回目の実行では、あなたのプログラムはインタラクタから1回目の実行による情報、すなわち全光樹上の各光のラインの流れる方向を受け取り、それらの情報に基づいてKaruhaがNeriに伝えた神秘的な数字 $s$ を推測します。

入力

各テストケースには複数のテストデータが含まれます。入力の最初の行には二つの正の整数 $T, r$ ($1 \le T \le 10^4, r \in \{1, 2\}$) が含まれ、それぞれテストケース数とステージ番号を表します。各テストデータについて：

• $r = 1$ の場合：

  • 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$ の場合：

  • 1行目に一つの正の整数 $n$ ($3 \le n \le 30$) が入力され、全光樹に含まれる光の塊の数と神秘的な数字を表します。
  • 続いて $n - 1$ 行あり、各行に二つの正の整数 $u, v$ ($1 \le u, v \le n$) が入力され、光の塊 $u$ から光の塊 $v$ へ流れる光のラインを表します。
  • あなたは直ちに一つの正の整数を出力し、推測した神秘的な数字 $s$ を示さなければなりません。
  • 注意：
    • 単一のテストケース内でのテストデータの入力順序は、1回目の実行時と異なる場合があります。
    • 同一のテストデータにおいて、光のラインが入力される順序は2回の実行で一致しない可能性がありますが、光の塊の番号は変わりません。
    • 各テストデータについて、推測した神秘的な数字 $s$ を出力し、標準出力バッファをフラッシュした後にのみ、次のテストデータの入力を受け取ることができます。

入出力例

入力 1

2 1
7 21
1 6
3 5
2 4
3 4
1 2
6 7
9 59
1 2
1 4
3 4
3 5
3 8
5 6
6 7
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

注記

上記の出力に基づき、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

図 1: 第一組のテストデータ

図 2: 第二組のテストデータ

テストプログラムについて

配布されたスクリプト treedir_testing_tool.py を使用することで、ローカル環境でプログラムの正当性を検証し、詳細なインタラクション過程を出力できます。テストを行う際は、このスクリプトをコンパイル済みの実行ファイルと同じディレクトリに置き、ターミナルで以下のコマンドを実行してください。

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

ここで： -q, --quiet はオプション引数で、これを使用するとテストスクリプトは詳細なインタラクション過程を出力しなくなります。 data_file はテストスクリプトに提供する入力ファイルパスです。このファイルは以下の形式を満たす必要があります。 1行目に二つの非負の整数 $T, seed$ が含まれ、それぞれテストデータ数と、テスト順序および木内のエッジ順序をランダム化するためのシード値を表します。$seed = 0$ を指定した場合、ランダム化は行われません。 各テストデータの形式は、前述の「1回目の実行」の入力形式と完全に同じです。 program はコンパイル済みの実行ファイルのパスです。 arguments はその実行ファイルに渡す追加のコマンドライン引数です。

注意： 1. テストスクリプトと実際の評価用インタラクタの実装は完全には一致しません。ローカルでのテスト結果は最終的な判定基準ではなく、デバッグ段階の参考としてのみ使用してください。 2. テストスクリプトは data_file 内のデータに対して基本的な形式チェックのみを行い、問題の制約を合法的に満たしているかのチェックは行いません。 3. テストスクリプトはプログラムの時間やメモリ消費を監視しないため、問題の制限を満たしているかのテストには使用できません。