頂点の木 が与えられます。頂点には の番号が付いています。
同じ頂点を持つ二つの木 について、次の条件をともに満たす頂点集合 が存在しないとき、 と は にあるといいます。
誘導部分グラフの定義
グラフとその頂点集合 に対して、 に属する頂点と、両端点がともに に属する辺だけを残して得られるグラフを、 が誘導する部分グラフといいます。
と良い関係にある木 が存在するか判定し、存在するならその一例を構成してください。
入力は標準入力から次の形式で与えられます。
各テストケースについて、次のように出力してください。
条件を満たす が存在しない場合、1 行に を出力してください。
存在する場合、 行にわたって次の形式で出力してください。
各テストケースは次の形式で与えられます。
の 番目の辺は頂点 と を結びます。
出力した 本の辺 は、頂点 からなる木 を構成し、 と は良い関係になければなりません。
条件を満たす答えが複数存在する場合、どれを出力しても構いません。
| 4 | 48 | 追加の制約はありません。 |