String With Rings

Time Limit : 8 sec, Memory Limit : 65536 KB

両端にリングのついた紐を考える.リングは正整数が付いていて,紐を区別する.紐の両端のリングには異なる数 a, b が付けられる.これを,[a, b] と記述する.複数の紐があり,一方の紐と他方の紐のリングに付いている数が同じ場合,そのリングのところで,これらの紐をつなげることができて,つなげてできたものを鎖と呼ぶことにする.例えば,[1, 3] と [3, 4] という紐からは [1, 3, 4] という鎖ができる.紐と鎖や鎖同志も同じ整数が付いているリングのところでつなげることができるものとする.

例えば,鎖 [1, 3, 4] と紐 [5, 1] からは [5, 1, 3, 4] ができ,鎖 [1, 3, 4] と鎖 [2, 3, 5] からは, 中央でクロスしたような形になる.鎖 [1, 3, 4] と鎖 [4, 6, 1] からは, 輪の形ができる.

このように様々な形ができるが, そのうちの一部で,同じ数の付いたリングは一度だけたどるつながった複数の紐を鎖と呼ぶことにする.例えば,鎖 [1, 3, 4] と鎖[2, 3, 5] からできる,中央でクロスしたような形には, [1, 3, 5],[2, 3, 4] という鎖も含まれ,鎖 [1, 3, 4] と鎖 [4, 6, 1] からできる輪には, [1, 3, 4, 6],[3, 4, 6, 1],[4, 6, 1, 3]などの鎖が含まれる.

これらの鎖に対して,含まれる数の個数を長さと定義する. 与えられた複数の紐に対して,つなげられるものはすべてつなげると1つ以上の 鎖を含む形ができる.そのうちの最大の鎖の長さを求めるプログラムを作成せよ.

入力データ の最初の行には紐の個数である正整数 1 ≤ n ≤ 100 が書いてあり,つづく n 行のそれぞれには, 空白で区切られた 2 つの整数 a, b が書いてあり 1 ≤ a < b ≤ 100 となっている.各行の 2 つの整数は 1 つの紐の両端の整数を表わす.

入力例1 入力例2 入力例3
7 6 7
1 3 1 2 1 3
3 4 2 3 2 4
1 4 3 4 3 5
2 7 4 5 4 6
5 7 1 5 6 7
6 7 2 6 2 6
1 7 4 7
 
出力例1 出力例2 出力例3
564

入力

入力は複数のデータセットからなる.n が 0 のとき入力が終了する.データセットの数は 10 を超えない.

出力

データセットごとに、最大の鎖の長さを1行に出力する.

入力例

7
1 3
3 4
1 4
2 7
5 7
6 7
1 7
6
1 2
2 3
3 4
4 5
1 5
2 6
7
1 3
2 4
3 5
4 6
6 7
2 6
4 7
0

出力例

5
6
4

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Source: 5th Japanese Olympiad in Informatics , 2006-02-12
http://www.ioi-jp.org/