소셜 네트워크
시간 제한1초메모리 제한128 MB
전날까지의 친구 관계 정보만 이용해 친구의 친구에게 매일 친구 요청을 보내는 방식으로 전체가 친구가 되는 날짜와 하루씩 새로 생기는 친구 수를 구하는 문제입니다.
문제
소셜 네트워크에서 친구 관계가 빠르게 늘어나는 과정을 생각해 보자.
매일 각 사람은 그날이 시작되기 전에 이미 친구였던 사람들의 친구 목록을 확인한다. 친구의 친구로 확인된 사람에게 친구 요청을 보내며, 그 요청은 하루가 지나면 수락되어 새 친구 관계가 된다. 따라서 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번째 날까지 각 날에 새로 생기는 친구 관계의 수를 한 줄에 하나씩 출력한다.