FEJS

문제

Social networks on the Internet became a part of the everyday life. One of the interesting phenomena is that the number of friendship is increasing rapidly. According to the old “a friend of a friend is my friend”, each person every day checks the list of friends of his friends and adds new people to his list. It takes 1 day to confirm the new friendship. So, if A and B and friends then person A sees only friendships of person B that were made yesterday or before. 

All friendships are symmetric – if A is a friend of B then B is a friend of A. 

As social network we are observing in this task doesn't allow friendships to be broken at some point everyone will be friend to everyone. 

Write a program that will determine the number of days until that happens. For each day output the number of new friendships that were made that day. 

입력

The first line contains two integers N and M (1 ≤ N ≤ 50, 1 ≤ M ≤ N*(N–1)/2), the number of users and initial number of friendships. 

The next M lines contain two numbers each A and B (1 ≤ A ≤ N, 1 ≤ B ≤ N, A < B) that describe friendships between users A and B. Test data will be such that solution will always exist.

출력

In the first line output one integer, the number of days K until everyone will be friend to everyone. In each of the next K lines output one integer, the number of friendships that were made that day. 

3 2
1 2
2 3

1
1

5 4
1 2
2 3
3 4
4 5

2
3
3

5 4
1 2
1 3
1 4
1 5

1
6