레이팅 미적용4
両端にリングのついた紐を考える.リングは正整数が付いていて,紐を区別す
る.紐の両端のリングには異なる数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
5
6
4
問題4-1
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 75
6
4
問題4-1