Ttas の国には 頂点からなる森があり、頂点には の番号が付いている。各頂点には Ttas が 1 人ずつ立っている。
頂点 の Ttas は、 に接続する辺をすべて見ることができない。それ以外のすべての辺と頂点番号は見える。すべての Ttas は次の事実を知っている。
ある日 Dadas は全員に次の事実を公に宣言した。
この森には少なくとも 1 本の辺が存在する。
その後、日付を 1 日目から数え始める。毎日、すべての Ttas は前日までのすべての宣言を利用し、次のいずれかを同時に公に宣言する。
同じ日の他の Ttas の宣言を、その日の判断には利用できない。すべての宣言は以後全員に公開される。
実際の森の構造が与えられる。自分の頂点に接続する辺が少なくとも 1 本存在すると知っている Ttas が初めて現れる日を求めよ。
入力は次の形式で与えられる。
各テストケースについて、条件を満たす最初の日を 1 行に出力せよ。
各テストケースは次の形式で与えられる。
各 について、頂点 と頂点 を結ぶ無向辺が存在する。
