問題文

この問題はコミュニケーション問題（あなたの作成したプログラムが複数プロセスで動作し、ジャッジシステムとの入出力を介して対話を行う形式の問題）です。

Alice 、 Bob として以下の手続きを振る舞うプログラムを作成してください。手続きはフェーズ $1$ とフェーズ $2$ からなり、まずフェーズ $1$ を行った直後、続けてフェーズ $2$ を行います。

フェーズ $1$

• Alice と Bob は、ジャッジシステムから正整数 $N$ が与えられる。
• Alice と Bob はジャッジシステムに対し、正整数 $k$ を送信する。

フェーズ $2$

• Alice はジャッジシステムから、各頂点に $1$ から $N$ までの番号が振られた $N$ 頂点の木 $T$ が与えられる。
• Alice は Bob に対し、 $1$ 以上 $N$ 以下の整数からなる長さ $k$ の数列 $A = (A_1, A_2, \cdots, A_k)$ を送信する。
• Bob は、各頂点に $1$ から $N$ までの番号が振られた、 $T$ と等しい木を一つ解答する。

$2$ つの木 $T, T'$ が等しいとは、任意の $1 \leq u \lt v \leq N$ に対し、 $T$ 上の頂点対 $(u, v)$ を結ぶ辺が存在することと $T'$ 上の頂点対 $(u, v)$ を結ぶ辺が存在することが同値であることと定義します。

ここで、上記の問題を $T$ によらず正解する上で必要な $k$ の最小値を $k_{\min}$ とします。 フェーズ $1$ で Alice と Bob が出力する $k$ は $k_{\min}$ である必要があります。

制約

• $3 \leq N \leq 1000$
• 与えられる木 $T$ は、各頂点に $1$ から $N$ までの番号が振られた $N$ 頂点の木である。
• $N$ は整数。

入出力

この問題はコミュニケーション問題（あなたの作成したプログラムが複数プロセスで動作し、ジャッジシステムとの入出力を介して対話を行う形式の問題）です。
Alice として振る舞うあなたのプログラムと、Bob として振る舞うあなたのプログラムが、ジャッジシステムとの入出力を介して対話を行う形式の問題です。

まず、あなたのプログラムに対し、Alice または Bob である文字列 $\mathrm{player}$ が与えられるので、これを受け取ってください。

$\mathrm{player}$

ここで、 $\mathrm{player}$ が Alice の場合、あなたのプログラムは Alice として振る舞う必要があります。 逆に、 $\mathrm{player}$ が Bob の場合、あなたのプログラムは Bob として振る舞う必要があります。

その後、フェーズ $1$ 、フェーズ $2$ の順に手続きを行ってください。

フェーズ $1$

Alice と Bob との両方に、以下の形式で整数 $N$ が与えられます。

$N$

その後、Alice と Bob は、以下の形式で正整数 $k$ を出力してください。

$k$

ただし、以下の条件を満たす必要があります。

• $k$ は $1 \leq k \leq 2000$ を満たす整数。
• Alice の出力した $k$ と Bob の出力した $k$ は等しい。

上記の条件を満たさない場合、ジャッジは -1 を出力します。このとき、提出はすでに不正解と判定されています。 ジャッジシステムはこの時点で終了するため、あなたのプログラムも終了するのが望ましいです。

フェーズ $2$

Alice は、以下の形式で木 $T$ が与えられるので、これを受け取ってください。

$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

ここで、 $U_i, V_i$ は $1$ 以上 $N$ 以下の整数あり、各 $i ~ (1 \leq i \leq N - 1)$ について、頂点 $U_i$ と頂点 $V_i$ は辺で結ばれていることを表します。

その後、 Alice は以下の形式で $1$ 以上 $N$ 以下の整数からなる長さ $k$ の数列 $A = (A_1, A_2, \cdots, A_k)$ を出力してください。

$A_1$ $A_2$ $\ldots$ $A_k$

Alice が数列 $A$ を出力した後、 Bob は以下の形式で Alice の送信した $A$ が与えられます。

$A_1$ $A_2$ $\ldots$ $A_k$

その後、 Bob は以下の形式で木 $T$ と等しい木を一つ出力してください。

$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

ここで、 $U_i, V_i$ は $1$ 以上 $N$ 以下の整数ある必要があり、各 $i ~ (1 \leq i \leq N - 1)$ について、頂点 $U_i$ と頂点 $V_i$ は辺で結ばれていることを表します。

また $2$ つの木 $T, T'$ が等しいとは、任意の $1 \leq u \lt v \leq N$ に対し、 $T$ 上の頂点対 $(u, v)$ を結ぶ辺が存在することと $T'$ 上の頂点対 $(u, v)$ を結ぶ辺が存在することが同値であることと定義します。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• -1 を受け取ったらただちにプログラムを終了してください。終了させた場合のジャッジ結果は WA となりますが、終了しなかった場合、ジャッジ結果は不定です。
• 解答を出力し終えた時もただちにプログラムを終了してください。終了しなかった場合、ジャッジ結果は不定です。
• 余計な改行は不正なフォーマットの出力とみなされるため、行わないでください。

サンプル