시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 78 | 16 | 8 | 19.512% |
両端にリングのついた紐を考える.リングは正整数が付いていて,紐を区別す る.紐の両端のリングには異なる数 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 つの紐の両端の整数を表わす.
出力(最大の鎖の長さ)の後に改行を入れること.
7 1 3 3 4 1 4 2 7 5 7 6 7 1 7
5
6 1 2 2 3 3 4 4 5 1 5 2 6
6
7 1 3 2 4 3 5 4 6 6 7 2 6 4 7
4