入力

入力は以下の形式で標準入力から与えられる。

N
X_1 Y_1
X_2 Y_2
:
X_{2N+1} Y_{2N+1}

• 1 行目には点の数を表す整数 N(1 ≦ N ≦ 100,000) が与えられる。
• そのあと 2N+1 行には、点の位置の情報が与えられる。このうち i 行目には整数 X_i(1 ≦ X_i ≦ 2N+1),\ Y_i(1 ≦ Y_i ≦ 2N+1) が空白区切りで与えられ、これは i 番目の点の座標が (X_i,\ Y_i) であることを表す。
• i ≠ j ならば、X_i ≠ X_j または Y_i ≠ Y_j を満たす。

出力

出力は標準出力に行い、末尾に改行を入れること。

出力は 2N+1 行からなる。

i 行目には、i 番目の点を削除したとき、残りの 2N 個の点から N 組の仲良しペアを作れるならばOK、作れないならばNGと出力すること。

部分点

以下の制約を追加で満たすデータセットに正解した場合は 30 点が与えられる。

• すべての i(1 ≦ i ≦ 2N) について、X_i = X_{i+1} または Y_i = Y_{i+1} のどちらかを満たす。