소셜 네트워크

소셜 네트워크에서 친구 관계가 빠르게 늘어나는 과정을 생각해 보자.

매일 각 사람은 그날이 시작되기 전에 이미 친구였던 사람들의 친구 목록을 확인한다. 친구의 친구로 확인된 사람에게 친구 요청을 보내며, 그 요청은 하루가 지나면 수락되어 새 친구 관계가 된다. 따라서 A와 B가 이미 친구라면, A는 B가 전날까지 맺은 친구 관계만 볼 수 있다.

모든 친구 관계는 양방향이며, 한 번 맺어진 친구 관계는 사라지지 않는다.

사람 수와 처음 친구 관계가 주어질 때, 모든 두 사람이 서로 친구가 되기까지 며칠이 걸리는지 구하라. 또한 첫째 날부터 마지막 날까지 매일 새로 생기는 친구 관계의 수를 출력하라.

첫째 줄에 사람의 수 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번째 날까지 각 날에 새로 생기는 친구 관계의 수를 한 줄에 하나씩 출력한다.