시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 86 40 36 51.429%

문제

소셜 네트워크는 이제 우리 삶의 일부가 되어버렸다. 이러한 소셜 네트워크를 분석하는 김동규 석사과정은 흥미로운 현상을 발견했다. 바로 친구 관계의 수가 급속도로 증가한다는 것이다.

예로부터 우리의 조상님들은 "친구의 친구는 나의 친구"라고 했다. 사람들은 매일 조상님들의 말씀을 따르기 위해서 자신의 친구의 친구 목록을 확인하고, 이를 모두 자신의 친구로 추가한다. 친구 관계는 상대방이 수락을 해야 되고, 총 1일이 걸린다.

예를 들어, A와 B가 친구라면, A는 B가 어제 또는 그 이전에 만든 친구만 볼 수 있다.

모든 친구관계는 대칭이다. 즉, A와 B의 친구라면, B도 A의 친구이다.

김동규가 분석하는 소셜 네트워크에서는 한 번 친구 관계가 맺어졌으면, 이것을 깰 수 없다.

사람의 수와 지금 친구 관계가 주어졌을 때, 모든 사람이 서로 친구가 되는데 걸리는데 몇 일이 걸리는지 구하는 프로그램을 작성하시오. 또한, 매일 매일 새로운 친구 관계가 얼마나 생기는지 구해서 출력하시오.

입력

첫째 줄에 사람의 수 N과 처음 친구 관계의 수 M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ N*(N-1)/2)

둘째 줄부터 M개의 줄에는 두 정수 A와 B가 주어진다. (1 ≤ A ≤ N, 1 ≤ B ≤ N, A < B). 이것은 A와 B가 친구라는 것을 의미한다. 항상 모든 사람이 서로 친구가 될 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 모든 사람이 서로 친구가 되는데 몇 일이 걸리는지 출력한다. 이 값을 K라고 하자.

다음 K개의 줄에는 몇 명의 새로운 친구 관계가 생기는지, 첫째날부터, K번째 날까지 한 줄에 하나씩 출력한다. 

예제 입력 1

5 4
1 2
2 3
3 4
4 5

예제 출력 1

2
3
3
W3sicHJvYmxlbV9pZCI6IjMwOTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMxNWNcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWIyOTQgXHVjNzc0XHVjODFjIFx1YzZiMFx1YjlhYyBcdWMwYjZcdWM3NTggXHVjNzdjXHViZDgwXHVhYzAwIFx1YjQxOFx1YzViNFx1YmM4NFx1YjgzOFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWI5N2MgXHViZDg0XHVjMTFkXHVkNTU4XHViMjk0IFx1YWU0MFx1YjNkOVx1YWRkYyBcdWMxMWRcdWMwYWNcdWFjZmNcdWM4MTVcdWM3NDAgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1ZDYwNFx1YzBjMVx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YmMxNFx1Yjg1YyBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFlMDlcdWMxOGRcdWIzYzRcdWI4NWMgXHVjOTlkXHVhYzAwXHVkNTVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViODVjXHViZDgwXHVkMTMwIFx1YzZiMFx1YjlhY1x1Yzc1OCBcdWM4NzBcdWMwYzFcdWIyZDhcdWI0ZTRcdWM3NDAgJnF1b3Q7XHVjZTVjXHVhZDZjXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YjI5NCBcdWIwOThcdWM3NTggXHVjZTVjXHVhZDZjJnF1b3Q7XHViNzdjXHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YjllNFx1Yzc3YyBcdWM4NzBcdWMwYzFcdWIyZDhcdWI0ZTRcdWM3NTggXHViOWQwXHVjNTAwXHVjNzQ0IFx1YjUzMFx1Yjk3NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWNlNWNcdWFkNmMgXHViYWE5XHViODVkXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWNlMCwgXHVjNzc0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjZTVjXHVhZDZjXHViODVjIFx1Y2Q5NFx1YWMwMFx1ZDU1Y1x1YjJlNC4gXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YjI5NCBcdWMwYzFcdWIzMDBcdWJjMjlcdWM3NzQgXHVjMjE4XHViNzdkXHVjNzQ0IFx1ZDU3NFx1YzU3YyBcdWI0MThcdWFjZTAsIFx1Y2QxZCAxXHVjNzdjXHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQVx1YzY0MCBCXHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yjc3Y1x1YmE3NCwgQVx1YjI5NCBCXHVhYzAwIFx1YzViNFx1YzgxYyBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzgwNFx1YzVkMCBcdWI5Y2NcdWI0ZTAgXHVjZTVjXHVhZDZjXHViOWNjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhYThcdWI0ZTAgXHVjZTVjXHVhZDZjXHVhZDAwXHVhY2M0XHViMjk0IFx1YjMwMFx1Y2U2ZFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBBXHVjNjQwIEJcdWM3NTggXHVjZTVjXHVhZDZjXHViNzdjXHViYTc0LCBCXHViM2M0IEFcdWM3NTggXHVjZTVjXHVhZDZjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFlNDBcdWIzZDlcdWFkZGNcdWFjMDAgXHViZDg0XHVjMTFkXHVkNTU4XHViMjk0IFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNTVjIFx1YmM4OCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YjlmYVx1YzViNFx1Yzg0Y1x1YzczY1x1YmE3NCwgXHVjNzc0XHVhYzgzXHVjNzQ0IFx1YWU3MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHVjNjQwIFx1YzljMFx1YWUwOCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTFjXHViODVjIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWI0MThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0XHViMzcwIFx1YmE4NyBcdWM3N2NcdWM3NzQgXHVhYzc4XHViOWFjXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI2MTBcdWQ1NWMsIFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2MgXHVjMGM4XHViODVjXHVjNmI0IFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNWJjXHViOWM4XHViMDk4IFx1YzBkZFx1YWUzMFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NzRcdWMxMWMgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWNjOThcdWM3NGMgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDUwLCAxICZsZTsgTSAmbGU7IE4qKE4tMSlcLzIpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEgJmxlOyBOLCAxICZsZTsgQiAmbGU7IE4sIEEgJmx0OyBCKS4gXHVjNzc0XHVhYzgzXHVjNzQwIEFcdWM2NDAgQlx1YWMwMCBcdWNlNWNcdWFkNmNcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTFjXHViODVjIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuIiwib3V0cHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjZTVjXHVhZDZjXHVhYzAwIFx1YjQxOFx1YjI5NFx1YjM3MCBcdWJhODcgXHVjNzdjXHVjNzc0IFx1YWM3OFx1YjlhY1x1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDQgS1x1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJhODcgXHViYTg1XHVjNzU4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzBkZFx1YWUzMFx1YjI5NFx1YzljMCwgXHVjY2FiXHVjOWY4XHViMGEwXHViZDgwXHVkMTMwLCBLXHViYzg4XHVjOWY4IFx1YjBhMFx1YWU0Y1x1YzljMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwOTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGRUpTIiwiZGVzY3JpcHRpb24iOiI8cD5Tb2NpYWwgbmV0d29ya3Mgb24gdGhlIEludGVybmV0IGJlY2FtZSBhIHBhcnQgb2YgdGhlIGV2ZXJ5ZGF5IGxpZmUuIE9uZSBvZiB0aGUgaW50ZXJlc3RpbmcgcGhlbm9tZW5hIGlzIHRoYXQgdGhlIG51bWJlciBvZiBmcmllbmRzaGlwIGlzIGluY3JlYXNpbmcgcmFwaWRseS4gQWNjb3JkaW5nIHRvIHRoZSBvbGQgJmxkcXVvO2EgZnJpZW5kIG9mIGEgZnJpZW5kIGlzIG15IGZyaWVuZCZyZHF1bzssIGVhY2ggcGVyc29uIGV2ZXJ5IGRheSBjaGVja3MgdGhlIGxpc3Qgb2YgZnJpZW5kcyBvZiBoaXMgZnJpZW5kcyBhbmQgYWRkcyBuZXcgcGVvcGxlIHRvIGhpcyBsaXN0LiBJdCB0YWtlcyAxIGRheSB0byBjb25maXJtIHRoZSBuZXcgZnJpZW5kc2hpcC4gU28sIGlmIEEgYW5kIEIgYW5kIGZyaWVuZHMgdGhlbiBwZXJzb24gQSBzZWVzIG9ubHkgZnJpZW5kc2hpcHMgb2YgcGVyc29uIEIgdGhhdCB3ZXJlIG1hZGUgeWVzdGVyZGF5IG9yIGJlZm9yZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWxsIGZyaWVuZHNoaXBzIGFyZSBzeW1tZXRyaWMgJm5kYXNoOyBpZiBBIGlzIGEgZnJpZW5kIG9mIEIgdGhlbiBCIGlzIGEgZnJpZW5kIG9mIEEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzIHNvY2lhbCBuZXR3b3JrIHdlIGFyZSBvYnNlcnZpbmcgaW4gdGhpcyB0YXNrIGRvZXNuJiMzOTt0IGFsbG93IGZyaWVuZHNoaXBzIHRvIGJlIGJyb2tlbiBhdCBzb21lIHBvaW50IGV2ZXJ5b25lIHdpbGwgYmUgZnJpZW5kIHRvIGV2ZXJ5b25lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGRldGVybWluZSB0aGUgbnVtYmVyIG9mIGRheXMgdW50aWwgdGhhdCBoYXBwZW5zLiBGb3IgZWFjaCBkYXkgb3V0cHV0IHRoZSBudW1iZXIgb2YgbmV3IGZyaWVuZHNoaXBzIHRoYXQgd2VyZSBtYWRlIHRoYXQgZGF5LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0gKDEgJmxlOyBOICZsZTsgNTAsIDEgJmxlOyBNICZsZTsgTiooTiZuZGFzaDsxKVwvMiksIHRoZSBudW1iZXIgb2YgdXNlcnMgYW5kIGluaXRpYWwgbnVtYmVyIG9mIGZyaWVuZHNoaXBzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBNIGxpbmVzIGNvbnRhaW4gdHdvIG51bWJlcnMgZWFjaCBBIGFuZCBCICgxICZsZTsgQSAmbGU7IE4sIDEgJmxlOyBCICZsZTsgTiwgQSAmbHQ7IEIpIHRoYXQgZGVzY3JpYmUgZnJpZW5kc2hpcHMgYmV0d2VlbiB1c2VycyBBIGFuZCBCLiBUZXN0IGRhdGEgd2lsbCBiZSBzdWNoIHRoYXQgc29sdXRpb24gd2lsbCBhbHdheXMgZXhpc3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb3V0cHV0IG9uZSBpbnRlZ2VyLCB0aGUgbnVtYmVyIG9mIGRheXMgSyB1bnRpbCBldmVyeW9uZSB3aWxsIGJlIGZyaWVuZCB0byBldmVyeW9uZS4gSW4gZWFjaCBvZiB0aGUgbmV4dCBLIGxpbmVzIG91dHB1dCBvbmUgaW50ZWdlciwgdGhlIG51bWJlciBvZiBmcmllbmRzaGlwcyB0aGF0IHdlcmUgbWFkZSB0aGF0IGRheS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=