시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 442 202 160 55.363%

문제

재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재석이는 그 중에 하나에 숨어야 한다. 헛간의 개수는 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+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhY2ZjIE1cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTVx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgQV9pXHVjNjQwIEJfaVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWQ1NWNcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWMwXHViYTcwLCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVjOWMwXHVjNWI0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjY2FiXHViYzg4XHVjOWY4XHViMjk0IFx1YzIyOFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVkNWRiXHVhYzA0IFx1YmM4OFx1ZDYzOFx1Yjk3YyhcdWI5Y2NcdWM1N2QgXHVhYzcwXHViOWFjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWQ1ZGJcdWFjMDRcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjXHViYTc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVkNWRiXHVhYzA0IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQpLCBcdWI0NTBcdWJjODhcdWM5ZjhcdWIyOTQgXHVhZGY4IFx1ZDVkYlx1YWMwNFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MsIFx1YzEzOFx1YmM4OFx1YzlmOFx1YjI5NCBcdWFkZjggXHVkNWRiXHVhYzA0XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhYzE2XHViMjk0IFx1ZDVkYlx1YWMwNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWIxOGRcdWM3YTVcdWM3NTggXHVjODcwXHVhYzEwXHViM2M0XHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgICAxLS0yLS01XHJcbiAgICAgICAgICAgICAgICAgICB8IFwvfFxyXG4gICAgICAgICAgICAgICAgICAgfFwvIHxcclxuICAgICAgICAgICAgICAgICAgIDMtLTRcclxuICAgICAgICAgICAgICAgICAgIHxcclxuICAgICAgICAgICAgICAgICAgIDY8XC9wcmU+XHJcblxyXG48cD5cdWQ1ZGJcdWFjMDQgNCwgNSwgNlx1Yzc0MCBcdWJhYThcdWI0NTAgMlx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhYzAwXHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgNFx1YmM4OCBcdWQ1ZGJcdWFjMDRcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWQ1ZGJcdWFjMDRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjExOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhpZGUgYW5kIFNlZWsiLCJkZXNjcmlwdGlvbiI6IjxwPkJlc3NpZSBpcyBwbGF5aW5nIGhpZGUgYW5kIHNlZWsgKGEgZ2FtZSBpbiB3aGljaCBhIG51bWJlciBvZiBwbGF5ZXJzIGhpZGUgYW5kIGEgc2luZ2xlIHBsYXllciAodGhlIHNlZWtlcikgYXR0ZW1wdHMgdG8gZmluZCB0aGVtIGFmdGVyIHdoaWNoIHZhcmlvdXMgcGVuYWx0aWVzIGFuZCByZXdhcmRzIGFyZSBhc3Nlc3NlZDsgbXVjaCBmdW4gdXN1YWxseSBlbnN1ZXMpLjxcL3A+XHJcblxyXG48cD5TaGUgaXMgdHJ5aW5nIHRvIGZpZ3VyZSBvdXQgaW4gd2hpY2ggb2YgTiAoMiAmbHQ7PSBOICZsdDs9IDIwLDAwMCkgYmFybnMgY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4gc2hlIHNob3VsZCBoaWRlLiBTaGUga25vd3MgdGhhdCBGSiAodGhlIHNlZWtlcikgc3RhcnRzIG91dCBpbiBiYXJuIDEuIEFsbCB0aGUgYmFybnMgYXJlIGNvbm5lY3RlZCBieSBNICgxICZsdDs9IE0gJmx0Oz0gNTAsMDAwKSBiaWRpcmVjdGlvbmFsIHBhdGhzIHdpdGggZW5kcG9pbnRzIEFfaSBhbmQgQl9pICgxICZsdDs9IEFfaSAmbHQ7PSBOOyAxICZsdDs9IEJfaSAmbHQ7PSBOOyBBX2kgIT0gQl9pKTsgaXQgaXMgcG9zc2libGUgdG8gcmVhY2ggYW55IGJhcm4gZnJvbSBhbnkgb3RoZXIgdGhyb3VnaCB0aGUgcGF0aHMuPFwvcD5cclxuXHJcbjxwPkJlc3NpZSBkZWNpZGVzIHRoYXQgaXQgd2lsbCBiZSBzYWZlc3QgdG8gaGlkZSBpbiB0aGUgYmFybiB0aGF0IGhhcyB0aGUgZ3JlYXRlc3QgZGlzdGFuY2UgZnJvbSBiYXJuIDEgKHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byBiYXJucyBpcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHBhdGhzIHRoYXQgb25lIG11c3QgdHJhdmVyc2UgdG8gZ2V0IGZyb20gb25lIHRvIHRoZSBvdGhlcikuIEhlbHAgQmVzc2llIGZpZ3VyZSBvdXQgdGhlIGJlc3QgYmFybiBpbiB3aGljaCB0byBoaWRlLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIE08XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTSsxOiBMaW5lIGkrMSBjb250YWlucyB0aGUgZW5kcG9pbnRzIGZvciBwYXRoIGk6IEFfaSBhbmQgQl9pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IE9uIGEgc2luZ2xlIGxpbmUsIHByaW50IHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogdGhlIGluZGV4IG9mIHRoZSBiYXJuIGZhcnRoZXN0IGZyb20gYmFybiAxIChpZiB0aGVyZSBhcmUgbXVsdGlwbGUgc3VjaCBiYXJucywgcHJpbnQgdGhlIHNtYWxsZXN0IHN1Y2ggaW5kZXgpLCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHBhdGhzIG5lZWRlZCB0byByZWFjaCB0aGlzIGJhcm4gZnJvbSBiYXJuIDEsIGFuZCB0aGUgbnVtYmVyIG9mIGJhcm5zIHdpdGggdGhpcyBudW1iZXIgb2YgcGF0aHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBmYXJtIGxheW91dCBpcyBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgICAgMS0tMi0tNVxyXG4gICAgICAgICAgICAgICAgICAgfCBcL3xcclxuICAgICAgICAgICAgICAgICAgIHxcLyB8XHJcbiAgICAgICAgICAgICAgICAgICAzLS00XHJcbiAgICAgICAgICAgICAgICAgICB8XHJcbiAgICAgICAgICAgICAgICAgICA2PFwvcHJlPlxyXG5cclxuPHA+QmFybnMgNCwgNSwgYW5kIDYgYXJlIGFsbCBhIGRpc3RhbmNlIG9mIDIgZnJvbSBiYXJuIDEuIFdlIGNob29zZSBiYXJuIDQgYmVjYXVzZSBpdCBoYXMgdGhlIHNtYWxsZXN0IGluZGV4LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d