Social Network

Consider a social network where friendships grow rapidly.

Every day, each person checks the friend lists of the people who were already their friends before that day begins. If someone is found as a friend of a friend, a friend request is sent, and the request is accepted after one day, creating a new friendship. Therefore, if A and B are already friends, A can only see the friendships that B had made by the previous day.

All friendships are bidirectional, and once a friendship is created, it never disappears.

Given the number of people and the initial friendships, determine how many days it takes until every pair of people are friends. Also output how many new friendships are created on each day from the first day through the last day.

The first line contains the number of people N and the number of initial friendships M. (1 <= N <= 50, 1 <= M <= N*(N-1)/2)

Each of the next M lines contains two integers A and B. (1 <= A <= N, 1 <= B <= N, A < B) This means A and B are friends initially.

Only inputs where everyone can eventually become friends with everyone else are given.

On the first line, output K, the number of days needed until every pair of people are friends.

On each of the next K lines, output the number of new friendships created on that day, from day 1 through day K.