시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB320262225.581%

문제

상그니 아라비아는 세계에서 오일 머니를 가장 많이 보유하는 나라이다. 국왕으로 재직중인 고둘라 창지즈 영사우드는 천연 자원의 위대함을 알리기 위해서 자전거 레이싱 경기를 개최하기로 결심했다. 

이 나라에는 도시가 N개가 있으며, 그 도시는 M개의 양방향 도로로 연결되어 있다. 도시는 1번부터 N번까지 번호가 매겨져 있다. 자전거 레이싱 트랙을 결정하기 위해서, 상근이는 아래와 같은 용어 세 가지를 사용할 것이다.

  • 경로는 각 도로의 도착점과 다음 도로의 시작점이 같은 도로의 연속이다.
  • 단순 경로는 한 도시를 두 번 이상 방문하지 않는 경로이다.
  • 링은 시작 도시와 끝나는 도시가 같은 단순 경로이다.

모든 도시 쌍 사이에는 적어도 하나의 경로가 있으며, 모든 도로는 많아야 한 링에 속한다.

다음 두 가지 조건을 만족하는 가장 긴 레이싱 경로를 찾는 프로그램을 작성하시오.

  • 경로의 시작 도시는 어느 곳이 되어도 상관없지만, 도착 도시는 1이어야 한다.
  • 한 도시를 한 번 이상 방문해도 된다. 하지만, 도로는 최대 한 번만 지날 수 있다.

입력

첫째 줄에 도시와 도로의 수 N과 M이 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 2N-2)

다음 M개 줄에는 서로 다른 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ N) 두 숫자는 도로의 정보를 나타내며, A와 B를 연결하는 양방향 도로이다. 두 도시를 연결하는 도로가 두 개 이상인 경우는 없다.

출력

첫째 줄에 가장 긴 레이싱 경로의 길이를 출력한다.

예제 입력 1

4 3
1 2
1 3
2 4

예제 출력 1

2

예제 입력 2

6 6
1 2
1 3
2 4
3 4
3 5
5 6

예제 출력 2

5

예제 입력 3

5 6
1 2
2 3
3 4
4 5
5 3
3 1

예제 출력 3

6
W3sicHJvYmxlbV9pZCI6IjMwMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZjhcdWIyYzggXHVjNTQ0XHViNzdjXHViZTQ0XHVjNTQ0XHViMjk0IFx1YzEzOFx1YWNjNFx1YzVkMFx1YzExYyBcdWM2MjRcdWM3N2MgXHViYTM4XHViMmM4XHViOTdjIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NzQgXHViY2Y0XHVjNzIwXHVkNTU4XHViMjk0IFx1YjA5OFx1Yjc3Y1x1Yzc3NFx1YjJlNC4gXHVhZDZkXHVjNjU1XHVjNzNjXHViODVjIFx1YzdhY1x1YzljMVx1YzkxMVx1Yzc3OCBcdWFjZTBcdWI0NThcdWI3N2MgXHVjYzNkXHVjOWMwXHVjOTg4IFx1YzYwMVx1YzBhY1x1YzZiMFx1YjRkY1x1YjI5NCBcdWNjOWNcdWM1ZjAgXHVjNzkwXHVjNmQwXHVjNzU4IFx1YzcwNFx1YjMwMFx1ZDU2OFx1Yzc0NCBcdWM1NGNcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1Yzc5MFx1YzgwNFx1YWM3MCBcdWI4MDhcdWM3NzRcdWMyZjEgXHVhY2JkXHVhZTMwXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWMyZWNcdWQ1ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWIwOThcdWI3N2NcdWM1ZDBcdWIyOTQgXHViM2M0XHVjMmRjXHVhYzAwIE5cdWFjMWNcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFkZjggXHViM2M0XHVjMmRjXHViMjk0IE1cdWFjMWNcdWM3NTggXHVjNTkxXHViYzI5XHVkNWE1IFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWIzYzRcdWMyZGNcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3OTBcdWM4MDRcdWFjNzAgXHViODA4XHVjNzc0XHVjMmYxIFx1ZDJiOFx1Yjc5OVx1Yzc0NCBcdWFjYjBcdWM4MTVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM2YTlcdWM1YjQgXHVjMTM4IFx1YWMwMFx1YzljMFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWFjMDEgXHViM2M0XHViODVjXHVjNzU4IFx1YjNjNFx1Y2MyOVx1YzgxMFx1YWNmYyBcdWIyZTRcdWM3NGMgXHViM2M0XHViODVjXHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzgxMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHViM2M0XHViODVjXHVjNzU4IFx1YzVmMFx1YzE4ZFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMmU4XHVjMjFjIFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWQ1NWMgXHViM2M0XHVjMmRjXHViOTdjIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHViODVjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5YzFcdWM3NDAgXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkY1x1YzY0MCBcdWIwNWRcdWIwOThcdWIyOTQgXHViM2M0XHVjMmRjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWIyZThcdWMyMWMgXHVhY2JkXHViODVjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGMgXHVjMzBkIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViOWNlXHVjNTQ0XHVjNTdjIFx1ZDU1YyBcdWI5YzFcdWM1ZDAgXHVjMThkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHViNDUwIFx1YWMwMFx1YzljMCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViODA4XHVjNzc0XHVjMmYxIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWFjYmRcdWI4NWNcdWM3NTggXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkY1x1YjI5NCBcdWM1YjRcdWIyOTAgXHVhY2YzXHVjNzc0IFx1YjQxOFx1YzViNFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWM5YzBcdWI5Y2MsIFx1YjNjNFx1Y2MyOSBcdWIzYzRcdWMyZGNcdWIyOTQgMVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI5N2MgXHVkNTVjIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViYzI5XHViYjM4XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVjOWMwXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNjQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyMTggTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAsMDAwLCAxICZsZTsgTSAmbGU7IDJOLTIpPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBLCBCICZsZTsgTikgXHViNDUwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgQVx1YzY0MCBCXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHVjNzc0XHViMmU0LiBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWFjMDAgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViODA4XHVjNzc0XHVjMmYxIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwMTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTVEFaQSIsImRlc2NyaXB0aW9uIjoiPHA+QSBiaWN5Y2xlIHJhY2UgaXMgYmVpbmcgb3JnYW5pemVkIGluIGEgY291bnRyeS4gVGhlIHRyYW5zcG9ydCBuZXR3b3JrIG9mIHRoZSBjb3VudHJ5IGNvbnNpc3RzIG9mIE4gY2l0aWVzIG51bWJlcmVkIDEgdGhyb3VnaCBOLCB3aXRoIE0gYmlkaXJlY3Rpb25hbCByb2FkcyBjb25uZWN0aW5nIHRoZW0uIFdlIHdpbGwgdXNlIHRoZSBmb2xsb3dpbmcgdGVybXM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QSBwYXRoIGlzIGEgc2VxdWVuY2Ugb2Ygcm9hZHMgaW4gd2hpY2ggZWFjaCByb2FkIHN0YXJ0cyBpbiB0aGUgY2l0eSB0aGUgcHJlY2VkaW5nIHJvYWQgZW5kZWQgaW4uJm5ic3A7PFwvbGk+XHJcblx0PGxpPkEgc2ltcGxlIHBhdGggaXMgYSBwYXRoIHdoaWNoIG5ldmVyIHZpc2l0cyBhIGNpdHkgbW9yZSB0aGFuIG9uY2UuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkEgcmluZyBpcyBhIHNpbXBsZSBwYXRoIGVuZGluZyBpbiB0aGUgc2FtZSBjaXR5IGl0IHN0YXJ0ZWQgaW4uJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIG5ldHdvcmsgaXMgc3VjaCB0aGF0IHRoZXJlIGlzIGF0IGxlYXN0IG9uZSBwYXRoIGJldHdlZW4gZXZlcnkgcGFpciBvZiBjaXRpZXMuIEFkZGl0aW9uYWxseSwgZXZlcnkgcm9hZCBpbiB0aGUgbmV0d29yayBpcyBwYXJ0IG9mIGF0IG1vc3Qgb25lIHJpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBmaW5kIHRoZSBsb25nZXN0IHBhdGggZm9yIHRoZSByYWNlIHNhdGlzZnlpbmcgdHdvIGNvbnN0cmFpbnRzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBwYXRoIG1heSBiZWdpbiBpbiBhbnkgY2l0eSwgYnV0IG11c3QgZW5kIGluIGNpdHkgMS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIHBhdGggbWF5IHZpc2l0IGEgY2l0eSBtb3JlIHRoYW4gb25jZSwgYnV0IGl0IG11c3Qgbm90IGNvbnRhaW4gYW55IHJvYWQgbW9yZSB0aGFuIG9uY2UuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNICgyICZsZTsgTiAmbGU7IDEwIDAwMCwgMSAmbGU7IE0gJmxlOyAyTi0yKSAmbmRhc2g7IHRoZSBudW1iZXJzIG9mIGNpdGllcyBhbmQgcm9hZHMgaW4gdGhlIG5ldHdvcmsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHR3byBkaWZmZXJlbnQgaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEsIEIgJmxlOyBOKS4gVGhlc2UgbnVtYmVycyBpbmRpY2F0ZSB0aGF0IHRoZXJlIGlzIGEgYmlkaXJlY3Rpb25hbCByb2FkIGJldHdlZW4gY2l0aWVzIEEgYW5kIEIuIE5vIHR3byBjaXRpZXMgd2lsbCBiZSBkaXJlY3RseSBjb25uZWN0ZWQgYnkgbW9yZSB0aGFuIG9uZSByb2FkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHJhY2UgcGF0aCBvbiBhIHNpbmdsZSBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #1 6번