시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 92 45 41 53.947%

문제

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

예로부터 우리의 조상님들은 "친구의 친구는 나의 친구"라고 했다. 사람들은 매일 조상님들의 말씀을 따르기 위해서 자신의 친구의 친구 목록을 확인하고, 이를 모두 자신의 친구로 추가한다. 친구 관계는 상대방이 수락을 해야 되고, 총 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+XHJcblxyXG48cD5cclxuXHRcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHVjNjQwIFx1YzljMFx1YWUwOCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTFjXHViODVjIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWI0MThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0XHViMzcwIFx1YmE3MFx1Y2U2MFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjYxMFx1ZDU1YywgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3YyBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM1YmNcdWI5YzhcdWIwOTggXHVjMGRkXHVhZTMwXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU3NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1Y2M5OFx1Yzc0YyBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTAsIDEgJmxlOyBNICZsZTsgTiooTi0xKVwvMik8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSAmbGU7IE4sIDEgJmxlOyBCICZsZTsgTiwgQSAmbHQ7IEIpLiBcdWM3NzRcdWFjODNcdWM3NDAgQVx1YzY0MCBCXHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjZTVjXHVhZDZjXHVhYzAwIFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG4iLCJvdXRwdXQiOiJcclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzExY1x1Yjg1YyBcdWNlNWNcdWFkNmNcdWFjMDAgXHViNDE4XHViMjk0XHViMzcwIFx1YmE3MFx1Y2U2MFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQ0IEtcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYTg3IFx1YmE4NVx1Yzc1OCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWMwZGRcdWFlMzBcdWIyOTRcdWM5YzAsIFx1Y2NhYlx1YzlmOFx1YjBhMFx1YmQ4MFx1ZDEzMCwgS1x1YmM4OFx1YzlmOCBcdWIwYTBcdWFlNGNcdWM5YzAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRkVKUyIsImRlc2NyaXB0aW9uIjoiPHA+U29jaWFsIG5ldHdvcmtzIG9uIHRoZSBJbnRlcm5ldCBiZWNhbWUgYSBwYXJ0IG9mIHRoZSBldmVyeWRheSBsaWZlLiBPbmUgb2YgdGhlIGludGVyZXN0aW5nIHBoZW5vbWVuYSBpcyB0aGF0IHRoZSBudW1iZXIgb2YgZnJpZW5kc2hpcCBpcyBpbmNyZWFzaW5nIHJhcGlkbHkuIEFjY29yZGluZyB0byB0aGUgb2xkICZsZHF1bzthIGZyaWVuZCBvZiBhIGZyaWVuZCBpcyBteSBmcmllbmQmcmRxdW87LCBlYWNoIHBlcnNvbiBldmVyeSBkYXkgY2hlY2tzIHRoZSBsaXN0IG9mIGZyaWVuZHMgb2YgaGlzIGZyaWVuZHMgYW5kIGFkZHMgbmV3IHBlb3BsZSB0byBoaXMgbGlzdC4gSXQgdGFrZXMgMSBkYXkgdG8gY29uZmlybSB0aGUgbmV3IGZyaWVuZHNoaXAuIFNvLCBpZiBBIGFuZCBCIGFuZCBmcmllbmRzIHRoZW4gcGVyc29uIEEgc2VlcyBvbmx5IGZyaWVuZHNoaXBzIG9mIHBlcnNvbiBCIHRoYXQgd2VyZSBtYWRlIHllc3RlcmRheSBvciBiZWZvcmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFsbCBmcmllbmRzaGlwcyBhcmUgc3ltbWV0cmljICZuZGFzaDsgaWYgQSBpcyBhIGZyaWVuZCBvZiBCIHRoZW4gQiBpcyBhIGZyaWVuZCBvZiBBLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BcyBzb2NpYWwgbmV0d29yayB3ZSBhcmUgb2JzZXJ2aW5nIGluIHRoaXMgdGFzayBkb2VzbiYjMzk7dCBhbGxvdyBmcmllbmRzaGlwcyB0byBiZSBicm9rZW4gYXQgc29tZSBwb2ludCBldmVyeW9uZSB3aWxsIGJlIGZyaWVuZCB0byBldmVyeW9uZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIG51bWJlciBvZiBkYXlzIHVudGlsIHRoYXQgaGFwcGVucy4gRm9yIGVhY2ggZGF5IG91dHB1dCB0aGUgbnVtYmVyIG9mIG5ldyBmcmllbmRzaGlwcyB0aGF0IHdlcmUgbWFkZSB0aGF0IGRheS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNICgxICZsZTsgTiAmbGU7IDUwLCAxICZsZTsgTSAmbGU7IE4qKE4mbmRhc2g7MSlcLzIpLCB0aGUgbnVtYmVyIG9mIHVzZXJzIGFuZCBpbml0aWFsIG51bWJlciBvZiBmcmllbmRzaGlwcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTSBsaW5lcyBjb250YWluIHR3byBudW1iZXJzIGVhY2ggQSBhbmQgQiAoMSAmbGU7IEEgJmxlOyBOLCAxICZsZTsgQiAmbGU7IE4sIEEgJmx0OyBCKSB0aGF0IGRlc2NyaWJlIGZyaWVuZHNoaXBzIGJldHdlZW4gdXNlcnMgQSBhbmQgQi4gVGVzdCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IHNvbHV0aW9uIHdpbGwgYWx3YXlzIGV4aXN0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG91dHB1dCBvbmUgaW50ZWdlciwgdGhlIG51bWJlciBvZiBkYXlzIEsgdW50aWwgZXZlcnlvbmUgd2lsbCBiZSBmcmllbmQgdG8gZXZlcnlvbmUuIEluIGVhY2ggb2YgdGhlIG5leHQgSyBsaW5lcyBvdXRwdXQgb25lIGludGVnZXIsIHRoZSBudW1iZXIgb2YgZnJpZW5kc2hpcHMgdGhhdCB3ZXJlIG1hZGUgdGhhdCBkYXkuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d