これはマルチパスのインタラクティブな問題です。出力するたびに必ず出力バッファをフラッシュしてください。出力のフラッシュには以下が使用できます。

• C/C++: fflush(stdout) または cout.flush()
• Java および Kotlin: System.out.flush()
• Python: sys.stdout.flush()

古典的なオンラインマッチングゲームでは、グラフの辺が一つずつ提示されます。辺が提示されるたびに、その辺をマッチングに含めるかどうかを即座に、かつ取り消し不能な形で決定しなければなりません。あなたの目標は、選ばれたどの2つの辺も頂点を共有しないようにしつつ、選択された辺の総数を最大化することです。

あなたは名声を求める野心的な計算機科学者です。ご存知の通り、オンライン環境で最大マッチングを見つけることは、二部グラフのような単純なクラスのグラフであっても、高い確率で不可能であることが証明されています。しかし、他の人が根本的な障壁と見なす場所に、あなたは栄光への機会を見出しました。今日、あなたは木に対する長年の未解決問題を解決したと主張し、画期的なアルゴリズムを世界に公開する準備ができています。

ただ一つ問題があります。昨日、あなたは証明にバグを発見しましたが、それを修正する方法がまだ分かりません。スポットライトを浴びることを諦めきれないあなたは、デモンストレーションをマジックショーに変えることにしました。舞台裏に隠れたアシスタントが、ゲームが始まる前に $n$ 個の頂点を持つ木全体に関する小さなヒントを送信してくれます。

当初の計画は単純でした。アシスタントに各辺のクエリに対する答えを直接送らせるというものです。この目的のために、あなたは長さ $(n - 1)$ の単一のバイナリ文字列を受信できる秘密のイヤホンを設置しました。しかし、観客はあなたの「ブレイクスルー」に懐疑的です。事前に仕組まれたトリックを防ぐため、彼らは辺がランダムな順序で提示されることを要求しました。これは、あなたもアシスタントも予測や制御ができない順序です。

舞台は整いました。スポットライトはあなたに当たっています。さあ、チャンネルを変えることなく、あなたの主張を証明してください。

インタラクション

あなたのプログラムは各テストケースに対して2回実行されます。prepare ラウンドでは、あなたのプログラムはアシスタントとして動作します。play ラウンドでは、あなたのプログラムはあなた（マジシャン）として動作します。いずれのラウンドにおいても、あなたのプログラムはインタラクティブな手順として評価されます。

Prepare ラウンド

入力の1行目には prepare という単語が含まれます。2行目には頂点数 $n$ ($2 \le n \le 500$) が含まれます。続く $(n - 1)$ 行には、木における $u$ と $v$ ($1 \le u, v \le n, u < v$) を結ぶ無向辺を表す2つの整数が含まれます。

あなたは、0 と 1 のみからなる長さ $(n - 1)$ のバイナリ文字列 $s$ を1行で出力しなければなりません。これは2回目の play ラウンドに送信される文字列です。出力が指定された形式に従っていない場合、Wrong Answer 判定を受けます。

Play ラウンド

あなたのプログラムは play ラウンドのために再起動されます。

入力の1行目には play という単語が含まれます。2行目には整数 $n$ が含まれます。3行目には、prepare ラウンドで出力したバイナリ文字列 $s$ が含まれます。

その後、$(n - 1)$ ターンのゲームが始まります。各ターンにおいて、2つの整数 $u$ と $v$ ($1 \le u, v \le n, u < v$) を含む行が提供されます。応答として、take または ignore のいずれかを含む1行を出力してください。1回目のラウンドのすべての辺が一度ずつ提供され、辺の順序は $(n - 1)!$ 通りの順列から一様にランダムに選択されます。

無効な形式の出力があった場合、ゲームは即座に終了し、インタラクタからそれ以上の情報は提供されません。

正当性の評価

$M$ をあなたのプログラムが選択した辺の集合とします。どの頂点も2つ以上の選択された辺に接続しておらず、かつ $|M| = |M^*|$ （ここで $M^*$ はグラフの最大マッチング）である場合、許容されます。

サンプルテストを除き、テストケースは全部で50個あります。この問題を解くには、サンプルテストを含むすべてのテストケースで正解する必要があります。

すべてのシャッフルは、プログラムの出力を受け取る前に固定されることが保証されています。ランダム性は各テストケースに対して固定されており、擬似乱数生成器のシードを固定することで実装されています。

開発とテストを支援するためのテストツールが提供されています。

入出力例

入力例 1 (Pass 1)

prepare
3
1 2
1 3

出力例 1 (Pass 1)

00

入力例 1 (Pass 2)

play
3
00
1 3
1 2

出力例 1 (Pass 2)

take
ignore

注記

サンプル1の解説: $|M^*| = 1$ であるため、どの辺を選択しても許容され、ヒントは任意のもので構いません。

Figure 1. Magically Marked Matching Master