시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 141 15 12 24.490%

문제

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

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

1. 경로는 각 도로의 도착점과 다음 도로의 시작점이 같은 도로의 연속이다.

2. 단순 경로는 한 도시를 두 번 이상 방문하지 않는 경로이다.

3. 링은 시작 도시와 끝나는 도시가 같은 단순 경로이다.

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

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

1. 경로의 시작 도시는 어느 곳이 되어도 상관없지만, 도착 도시는 1이어야 한다.

2. 한 도시를 한 번 이상 방문해도 된다. 하지만, 도로는 최대 한 번만 지날 수 있다.

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjMwMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZjhcdWIyYzggXHVjNTQ0XHViNzdjXHViZTQ0XHVjNTQ0XHViMjk0IFx1YzEzOFx1YWNjNFx1YzVkMFx1YzExYyBcdWM2MjRcdWM3N2MgXHViYTM4XHViMmM4XHViOTdjIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NzQgXHViY2Y0XHVjNzIwXHVkNTU4XHViMjk0IFx1YjA5OFx1Yjc3Y1x1Yzc3NFx1YjJlNC4gXHVhZDZkXHVjNjU1XHVjNzNjXHViODVjIFx1YzdhY1x1YzljMVx1YzkxMVx1Yzc3OCBcdWFjZTBcdWI0NThcdWI3N2MgXHVjYzNkXHVjOWMwXHVjOTg4IFx1YzYwMVx1YzBhY1x1YzZiMFx1YjRkY1x1YjI5NCBcdWNjOWNcdWM1ZjAgXHVjNzkwXHVjNmQwXHVjNzU4IFx1YzcwNFx1YjMwMFx1ZDU2OFx1Yzc0NCBcdWM1NGNcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1Yzc5MFx1YzgwNFx1YWM3MCBcdWI4MDhcdWM3NzRcdWMyZjEgXHVhY2JkXHVhZTMwXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWMyZWNcdWQ1ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NCBcdWIwOThcdWI3N2NcdWM1ZDBcdWIyOTQgXHViM2M0XHVjMmRjXHVhYzAwIE5cdWFjMWNcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFkZjggXHViM2M0XHVjMmRjXHViMjk0IE1cdWFjMWNcdWM3NTggXHVjNTkxXHViYzI5XHVkNWE1IFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWIzYzRcdWMyZGNcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3OTBcdWM4MDRcdWFjNzAgXHViODA4XHVjNzc0XHVjMmYxIFx1ZDJiOFx1Yjc5OVx1Yzc0NCBcdWFjYjBcdWM4MTVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM2YTlcdWM1YjQgXHVjMTM4IFx1YWMwMFx1YzljMFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxLiBcdWFjYmRcdWI4NWNcdWIyOTQgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWIzYzRcdWNjMjlcdWM4MTBcdWFjZmMgXHViMmU0XHVjNzRjIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0Mi4gXHViMmU4XHVjMjFjIFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWQ1NWMgXHViM2M0XHVjMmRjXHViOTdjIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHViODVjXHVjNzc0XHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdDMuIFx1YjljMVx1Yzc0MCBcdWMyZGNcdWM3OTEgXHViM2M0XHVjMmRjXHVjNjQwIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzIxYyBcdWFjYmRcdWI4NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGMgXHVjMzBkIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViOWNlXHVjNTQ0XHVjNTdjIFx1ZDU1YyBcdWI5YzFcdWM1ZDAgXHVjMThkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgXHViNDUwIFx1YWMwMFx1YzljMCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViODA4XHVjNzc0XHVjMmYxIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MS4gXHVhY2JkXHViODVjXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWIzYzRcdWMyZGNcdWIyOTQgXHVjNWI0XHViMjkwIFx1YWNmM1x1Yzc3NCBcdWI0MThcdWM1YjRcdWIzYzQgXHVjMGMxXHVhZDAwXHVjNWM2XHVjOWMwXHViOWNjLCBcdWIzYzRcdWNjMjkgXHViM2M0XHVjMmRjXHViMjk0IDFcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdDIuIFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI5N2MgXHVkNTVjIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViYzI5XHViYjM4XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVjOWMwXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM2NDAgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMCwwMDAsIDEgJmxlOyBNICZsZTsgMk4tMik8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzgxNVx1YzIxOCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyBOKSBcdWI0NTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBBXHVjNjQwIEJcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWI4MDhcdWM3NzRcdWMyZjEgXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzAxNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNUQVpBIiwiZGVzY3JpcHRpb24iOiI8cD5BIGJpY3ljbGUgcmFjZSBpcyBiZWluZyBvcmdhbml6ZWQgaW4gYSBjb3VudHJ5LiBUaGUgdHJhbnNwb3J0IG5ldHdvcmsgb2YgdGhlIGNvdW50cnkgY29uc2lzdHMgb2YgTiBjaXRpZXMgbnVtYmVyZWQgMSB0aHJvdWdoIE4sIHdpdGggTSBiaWRpcmVjdGlvbmFsIHJvYWRzIGNvbm5lY3RpbmcgdGhlbS4gV2Ugd2lsbCB1c2UgdGhlIGZvbGxvd2luZyB0ZXJtczombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIHBhdGggaXMgYSBzZXF1ZW5jZSBvZiByb2FkcyBpbiB3aGljaCBlYWNoIHJvYWQgc3RhcnRzIGluIHRoZSBjaXR5IHRoZSBwcmVjZWRpbmcgcm9hZCBlbmRlZCBpbi4mbmJzcDs8XC9saT5cclxuXHQ8bGk+QSBzaW1wbGUgcGF0aCBpcyBhIHBhdGggd2hpY2ggbmV2ZXIgdmlzaXRzIGEgY2l0eSBtb3JlIHRoYW4gb25jZS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+QSByaW5nIGlzIGEgc2ltcGxlIHBhdGggZW5kaW5nIGluIHRoZSBzYW1lIGNpdHkgaXQgc3RhcnRlZCBpbi4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgbmV0d29yayBpcyBzdWNoIHRoYXQgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIHBhdGggYmV0d2VlbiBldmVyeSBwYWlyIG9mIGNpdGllcy4gQWRkaXRpb25hbGx5LCBldmVyeSByb2FkIGluIHRoZSBuZXR3b3JrIGlzIHBhcnQgb2YgYXQgbW9zdCBvbmUgcmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIGxvbmdlc3QgcGF0aCBmb3IgdGhlIHJhY2Ugc2F0aXNmeWluZyB0d28gY29uc3RyYWludHM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIHBhdGggbWF5IGJlZ2luIGluIGFueSBjaXR5LCBidXQgbXVzdCBlbmQgaW4gY2l0eSAxLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgcGF0aCBtYXkgdmlzaXQgYSBjaXR5IG1vcmUgdGhhbiBvbmNlLCBidXQgaXQgbXVzdCBub3QgY29udGFpbiBhbnkgcm9hZCBtb3JlIHRoYW4gb25jZS4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0gKDIgJmxlOyBOICZsZTsgMTAgMDAwLCAxICZsZTsgTSAmbGU7IDJOLTIpICZuZGFzaDsgdGhlIG51bWJlcnMgb2YgY2l0aWVzIGFuZCByb2FkcyBpbiB0aGUgbmV0d29yay4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdHdvIGRpZmZlcmVudCBpbnRlZ2VycyBBIGFuZCBCICgxICZsZTsgQSwgQiAmbGU7IE4pLiBUaGVzZSBudW1iZXJzIGluZGljYXRlIHRoYXQgdGhlcmUgaXMgYSBiaWRpcmVjdGlvbmFsIHJvYWQgYmV0d2VlbiBjaXRpZXMgQSBhbmQgQi4gTm8gdHdvIGNpdGllcyB3aWxsIGJlIGRpcmVjdGx5IGNvbm5lY3RlZCBieSBtb3JlIHRoYW4gb25lIHJvYWQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3QgcmFjZSBwYXRoIG9uIGEgc2luZ2xlIGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==