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つ以上の 鎖を含む形ができる.そのうちの最大の鎖の長さを求めるプログラムを作成せよ.

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

出力ファイルのファイル名は “output.txt” である.“output.txt” においては, 出力(最大の鎖の長さ)の後に改行を入れること.

入力例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

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


Notes on Submission

標準入出力を行うプログラムを作成して下さい。

上記の形式で複数のデータセットが与えられます。nが0のとき入力が終了します。

Sample Input

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

Sample Output

5
6
4

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