시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 851 402 308 54.513%

문제

재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재석이는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자.  

재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1<= M <= 50,000)개의 양방향 길로 이어져 있고, 그 양 끝을 A_i 와 B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)로 나타낸다. 또한 어떤 헛간에서 다른 헛간으로는 언제나 도달 가능하다고 생각해도 좋다. 

재서기는 발냄새가 지독하기 때문에 최대한 냄새가 안나게 숨을 장소를 찾고자 한다. 냄새는 1번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다. 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자!

입력

첫 번째 줄에는 N과 M이 공백을 사이에 두고 주어진다.

이후 M줄에 걸쳐서 A_i와 B_i가 공백을 사이에 두고 주어진다.

 

출력

출력은 한줄로 이루어지며, 세 개의 값을 공백으로 구분지어 출력해야한다. 

첫 번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력한다), 두 번째는 그 헛간까지의 거리를, 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야한다.

예제 입력 1

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

예제 출력 1

4 2 3

힌트

농장의 조감도는 아래와 같다. 

                   1--2--5
                   | /|
                   |/ |
                   3--4
                   |
                   6

헛간 4, 5, 6은 모두 2의 거리를 가진다. 여기서 4번 헛간을 선택하는 이유는 헛간의 번호가 가장 작기 때문이다.

W3sicHJvYmxlbV9pZCI6IjYxMTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMjhcdWJjMTRcdWFmMmRcdWM5YzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzdhY1x1YzExY1x1YWUzMFx1YjI5NCBcdWMyMThcdWQ2MDBcdWIyYzhcdWM2NDAgXHVhZDUwXHVjNjc4IFx1YjE4ZFx1YzdhNVx1YzVkMFx1YzExYyBcdWMyMjhcdWJjMTRcdWFmMmRcdWM5YzhcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViMThkXHVjN2E1XHVjNWQwXHViMjk0IFx1ZDVkYlx1YWMwNFx1Yzc3NCBcdWI5Y2VcdWM3NzQgXHViMTEwXHViODI0XHVjNzg4XHVhY2UwIFx1YzdhY1x1YzExZFx1Yzc3NFx1YjI5NCBcdWFkZjggXHVjOTExXHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzVkMCBcdWMyMjhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ1ZGJcdWFjMDRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IE4oMiAmbHQ7PSBOICZsdDs9IDIwLDAwMClcdWFjMWNcdWM3NzRcdWJhNzAsIDEgXHViZDgwXHVkMTMwIFx1YzBjY1x1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuICZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3YWNcdWMxMWNcdWFlMzBcdWIyOTQgXHVjMjE4XHVkNjAwXHViMmM4XHVhYzAwIDFcdWJjODggXHVkNWRiXHVhYzA0XHViZDgwXHVkMTMwIFx1Y2MzZVx1Yzc0NCBcdWFjODNcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1ZDVkYlx1YWMwNFx1Yzc0MCBNKDEmbHQ7PSBNICZsdDs9IDUwLDAwMClcdWFjMWNcdWM3NTggXHVjNTkxXHViYzI5XHVkNWE1IFx1YWUzOFx1Yjg1YyBcdWM3NzRcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFkZjggXHVjNTkxIFx1YjA1ZFx1Yzc0NCBBX2kgXHVjNjQwIEJfaSgxJmx0Oz0gQV9pICZsdDs9IE47IDEgJmx0Oz0gQl9pICZsdDs9IE47IEFfaSAhPSBCX2kpXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YzViNFx1YjVhNCBcdWQ1ZGJcdWFjMDRcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1ZDVkYlx1YWMwNFx1YzczY1x1Yjg1Y1x1YjI5NCBcdWM1YjhcdWM4MWNcdWIwOTggXHViM2M0XHViMmVjIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NzRcdWIzYzQgXHVjODhiXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3YWNcdWMxMWNcdWFlMzBcdWIyOTQgXHViYzFjXHViMGM0XHVjMGM4XHVhYzAwIFx1YzljMFx1YjNjNVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjBjNFx1YzBjOFx1YWMwMCBcdWM1NDhcdWIwOThcdWFjOGMgXHVjMjI4XHVjNzQ0IFx1YzdhNVx1YzE4Y1x1Yjk3YyBcdWNjM2VcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWIwYzRcdWMwYzhcdWIyOTQgMVx1YmM4OCBcdWQ1ZGJcdWFjMDRcdWM1ZDBcdWMxMWNcdWM3NTggXHVhYzcwXHViOWFjKFx1YzVlY1x1YWUzMFx1YzExYyBcdWFjNzBcdWI5YWNcdWI3N2MgXHVkNTY4XHVjNzQwIFx1YzljMFx1YjA5OFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhZTM4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQpXHVhYzAwIFx1YmE0MFx1YzViNFx1YzljOFx1YzIxOFx1Yjg1ZCBcdWFjMTBcdWMxOGNcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3YWNcdWMxMWNcdWFlMzBcdWM3NTggXHViYzFjXHViMGM0XHVjMGM4XHViOTdjIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWMyMjhcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1ZGJcdWFjMDRcdWM3NDQgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWFjOGMgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWNmYyBNXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE1cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIEFfaVx1YzY0MCBCX2lcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVkNTVjXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljMFx1YmE3MCwgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWFjMTJcdWM3NDQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YzljMFx1YzViNCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjhcdWIyOTQgXHVjMjI4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQ1ZGJcdWFjMDQgXHViYzg4XHVkNjM4XHViOTdjKFx1YjljY1x1YzU3ZCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1ZDVkYlx1YWMwNFx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWJhNzQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWQ1ZGJcdWFjMDQgXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNCksIFx1YjQ1MCBcdWJjODhcdWM5ZjhcdWIyOTQgXHVhZGY4IFx1ZDVkYlx1YWMwNFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MsIFx1YzEzOCBcdWJjODhcdWM5ZjhcdWIyOTQgXHVhZGY4IFx1ZDVkYlx1YWMwNFx1YWNmYyBcdWFjMTlcdWM3NDAgXHVhYzcwXHViOWFjXHViOTdjIFx1YWMxNlx1YjI5NCBcdWQ1ZGJcdWFjMDRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViMThkXHVjN2E1XHVjNzU4IFx1Yzg3MFx1YWMxMFx1YjNjNFx1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgICAgMS0tMi0tNVxyXG4gICAgICAgICAgICAgICAgICAgfCBcL3xcclxuICAgICAgICAgICAgICAgICAgIHxcLyB8XHJcbiAgICAgICAgICAgICAgICAgICAzLS00XHJcbiAgICAgICAgICAgICAgICAgICB8XHJcbiAgICAgICAgICAgICAgICAgICA2PFwvcHJlPlxyXG5cclxuPHA+XHVkNWRiXHVhYzA0IDQsIDUsIDZcdWM3NDAgXHViYWE4XHViNDUwIDJcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YWMwMFx1YzljNFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIDRcdWJjODggXHVkNWRiXHVhYzA0XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVkNWRiXHVhYzA0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYxMTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIaWRlIGFuZCBTZWVrIiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzaWUgaXMgcGxheWluZyBoaWRlIGFuZCBzZWVrIChhIGdhbWUgaW4gd2hpY2ggYSBudW1iZXIgb2YgcGxheWVycyBoaWRlIGFuZCBhIHNpbmdsZSBwbGF5ZXIgKHRoZSBzZWVrZXIpIGF0dGVtcHRzIHRvIGZpbmQgdGhlbSBhZnRlciB3aGljaCB2YXJpb3VzIHBlbmFsdGllcyBhbmQgcmV3YXJkcyBhcmUgYXNzZXNzZWQ7IG11Y2ggZnVuIHVzdWFsbHkgZW5zdWVzKS48XC9wPlxyXG5cclxuPHA+U2hlIGlzIHRyeWluZyB0byBmaWd1cmUgb3V0IGluIHdoaWNoIG9mIE4gKDIgJmx0Oz0gTiAmbHQ7PSAyMCwwMDApIGJhcm5zIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OIHNoZSBzaG91bGQgaGlkZS4gU2hlIGtub3dzIHRoYXQgRkogKHRoZSBzZWVrZXIpIHN0YXJ0cyBvdXQgaW4gYmFybiAxLiBBbGwgdGhlIGJhcm5zIGFyZSBjb25uZWN0ZWQgYnkgTSAoMSAmbHQ7PSBNICZsdDs9IDUwLDAwMCkgYmlkaXJlY3Rpb25hbCBwYXRocyB3aXRoIGVuZHBvaW50cyBBX2kgYW5kIEJfaSAoMSAmbHQ7PSBBX2kgJmx0Oz0gTjsgMSAmbHQ7PSBCX2kgJmx0Oz0gTjsgQV9pICE9IEJfaSk7IGl0IGlzIHBvc3NpYmxlIHRvIHJlYWNoIGFueSBiYXJuIGZyb20gYW55IG90aGVyIHRocm91Z2ggdGhlIHBhdGhzLjxcL3A+XHJcblxyXG48cD5CZXNzaWUgZGVjaWRlcyB0aGF0IGl0IHdpbGwgYmUgc2FmZXN0IHRvIGhpZGUgaW4gdGhlIGJhcm4gdGhhdCBoYXMgdGhlIGdyZWF0ZXN0IGRpc3RhbmNlIGZyb20gYmFybiAxICh0aGUgZGlzdGFuY2UgYmV0d2VlbiB0d28gYmFybnMgaXMgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBwYXRocyB0aGF0IG9uZSBtdXN0IHRyYXZlcnNlIHRvIGdldCBmcm9tIG9uZSB0byB0aGUgb3RoZXIpLiBIZWxwIEJlc3NpZSBmaWd1cmUgb3V0IHRoZSBiZXN0IGJhcm4gaW4gd2hpY2ggdG8gaGlkZS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBNPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk0rMTogTGluZSBpKzEgY29udGFpbnMgdGhlIGVuZHBvaW50cyBmb3IgcGF0aCBpOiBBX2kgYW5kIEJfaTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBPbiBhIHNpbmdsZSBsaW5lLCBwcmludCB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IHRoZSBpbmRleCBvZiB0aGUgYmFybiBmYXJ0aGVzdCBmcm9tIGJhcm4gMSAoaWYgdGhlcmUgYXJlIG11bHRpcGxlIHN1Y2ggYmFybnMsIHByaW50IHRoZSBzbWFsbGVzdCBzdWNoIGluZGV4KSwgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBwYXRocyBuZWVkZWQgdG8gcmVhY2ggdGhpcyBiYXJuIGZyb20gYmFybiAxLCBhbmQgdGhlIG51bWJlciBvZiBiYXJucyB3aXRoIHRoaXMgbnVtYmVyIG9mIHBhdGhzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgZmFybSBsYXlvdXQgaXMgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICAgIDEtLTItLTVcclxuICAgICAgICAgICAgICAgICAgIHwgXC98XHJcbiAgICAgICAgICAgICAgICAgICB8XC8gfFxyXG4gICAgICAgICAgICAgICAgICAgMy0tNFxyXG4gICAgICAgICAgICAgICAgICAgfFxyXG4gICAgICAgICAgICAgICAgICAgNjxcL3ByZT5cclxuXHJcbjxwPkJhcm5zIDQsIDUsIGFuZCA2IGFyZSBhbGwgYSBkaXN0YW5jZSBvZiAyIGZyb20gYmFybiAxLiBXZSBjaG9vc2UgYmFybiA0IGJlY2F1c2UgaXQgaGFzIHRoZSBzbWFsbGVzdCBpbmRleC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==