\(N\) 頂点の木があります。頂点には \(1\) から \(N\) までの番号が付いています。 頂点 \(i\) には整数 \(A_i\) が書かれており、\(A_i\) は \(0\) または \(1\) です。
Alice と Bob の \(2\) つのプログラムが協力して、両端に異なる整数が書かれた辺を \(1\) 本見つけます。 ただし、そのような辺が存在しない場合は、そのことを報告します。
はじめ、Alice は木の辺をすべて知っていますが、数列 \(A\) を知りません。 一方、Bob は数列 \(A\) を知っていますが、木の辺を知りません。 \(N\) は Alice と Bob の両方に知らされています。
Alice と Bob は、次の順に通信できます。
どのような木と数列 \(A\) が与えられても正しい答えを出力するプログラムを作成してください。
制約
この問題はインタラクティブ問題です。 Alice として振る舞うあなたのプログラムと、Bob として振る舞うあなたのプログラムが、ジャッジプログラムを介して通信します。
あなたのプログラムは、最初に以下の形式で入力を受け取ってください。
| \(\mathrm{Player}\) | |
| \(N\) |
ここで、\(\mathrm{Player}\) は文字列 Alice または文字列 Bob です。
Alice として振る舞うプログラムだけが、続いて木の辺を以下の形式で入力として受け取ります。
| \(u_1\) | \(v_1\) | |
| \(u_2\) | \(v_2\) | |
| \(\vdots\) | \(\vdots\) | |
| \(u_{N-1}\) | \(v_{N-1}\) |
Bob として振る舞うプログラムだけが、続いて数列 \(A\) を以下の形式で入力として受け取ります。
| \(A_1\) | \(A_2\) | \(\ldots\) | \(A_N\) |
まず、Alice は \(1,2,\ldots,N\) の順列 \(P=(P_1,P_2,\ldots,P_N)\) を、以下の形式で出力してください。
| \(P_1\) | \(P_2\) | \(\ldots\) | \(P_N\) |
Bob は、Alice が出力した順列を同じ形式で入力として受け取ります。 続いて、Bob は \(1\) 以上 \(N\) 以下の整数 \(K\) を以下の形式で出力してください。
| \(K\) |
Alice は、Bob が出力した整数 \(K\) を入力として受け取ります。 続いて、Alice は \(1\) 以上 \(N\) 以下の整数 \(X\) を以下の形式で出力してください。
| \(X\) |
Bob は、Alice が出力した整数 \(X\) を入力として受け取ります。 最後に Bob は答えを出力します。
両端に異なる整数が書かれた辺 \((a,b)\) を見つけた場合、以下の形式で出力してください。
| \(a\) | \(b\) |
そのような辺が存在しない場合、以下の形式で出力してください。
| \(-1\) |
答えを出力した後、プログラムを直ちに終了してください。答えに対する応答はありません。
出力形式が不正である場合、順列が条件を満たさない場合、範囲外の整数を出力した場合、または答えが誤っている場合、ジャッジ結果は Wrong Answer となります。 相手のプログラムの出力が不正であった場合、入力として \(-1\) が与えられることがあります。その場合、ただちにプログラムを終了してください。
入出力例
\(N=5\)、木の辺が \((1,2),(1,3),(3,4),(3,5)\)、\(A=(0,0,1,0,1)\) の場合の通信例を示します。
| Alice の入力 | Alice の出力 | Bob の入力 | Bob の出力 | 説明 |
| Alice | Bob | それぞれの役割が与えられます。 | ||
| 5 | 5 | 両方に \(N\) が与えられます。 | ||
| 1 2 | 0 0 1 0 1 | Alice に木が、Bob に \(A\) が与えられます。 | ||
| 1 3 | ||||
| 3 4 | ||||
| 3 5 | ||||
| 1 2 3 4 5 | Alice が順列を送ります。 | |||
| 1 2 3 4 5 | Bob が順列を受け取ります。 | |||
| 3 | Bob が整数を \(1\) つ送ります。 | |||
| 3 | Alice が整数を受け取ります。 | |||
| 1 | Alice が整数を \(1\) つ送ります。 | |||
| 1 | Bob が整数を受け取ります。 | |||
| 1 3 | Bob が答えを出力します。 |
この例は説明のためのものであり、正しい通信方法がこの例に限られるわけではありません。