모둠

KOI대학교 영재교육원에서 정보올림피아드에 관심이 있는 학생들을 위한 캠프를 연다. 캠프에 모인 학생들 사이에는 원래부터 서로 아는 경우가 있다.

교육원은 학생들을 생년월일이 빠른 순서로 나열한 뒤, 이 순서에서 연속한 구간마다 하나의 모둠을 만들려고 한다. 이상적인 분할에서는 같은 모둠에 속한 모든 학생 쌍이 서로 알고, 서로 다른 모둠에 속한 모든 학생 쌍은 서로 모른다. 하지만 이런 분할이 항상 가능한 것은 아니므로, 다음과 같은 분할 점수로 분할의 좋고 나쁨을 평가한다.

같은 모둠에 속했지만 서로 모르는 학생 쌍마다 1점을 더한다. 서로 다른 모둠에 속했지만 서로 아는 학생 쌍마다 1점을 더한다.

다음 그림은 8명의 학생을 3개의 모둠 A, B, C로 나누었을 때 분할 점수가 5가 되는 경우를 보여준다. 검은 점은 학생, 선은 서로 아는 관계, 점선 원은 모둠을 나타낸다. 학생은 생년월일이 빠른 순서대로 1번부터 8번까지 번호가 붙어 있다. 이 분할에서는 A와 B 사이에 아는 관계 3개, B와 C 사이에 아는 관계 1개가 있다. A와 B 내부의 모든 학생 쌍은 서로 알지만, C에서는 7번과 8번 사이에 아는 관계가 없다. 따라서 점수는 3+1+1=5이다.

다음처럼 두 개의 모둠으로 나누어도 분할 점수는 5이다.

다음처럼 네 개의 모둠으로 나누면 분할 점수는 8이다.

학생 사이의 아는 관계가 주어질 때, 분할 점수가 최소가 되는 모둠 분할을 구하는 프로그램을 작성하라. 모둠이 하나뿐인 분할도 허용된다.

첫째 줄에 학생 수 N이 주어진다. N은 2 이상 3,000 이하이다. 학생은 1번부터 N번까지 번호가 붙어 있으며, 번호가 작을수록 생년월일이 빠르다.

이어지는 N개의 줄에는 서로 아는 학생의 정보가 주어진다. 이 중 K번째 줄에는 학생 K가 알고 있는 학생들의 번호가 오름차순으로 주어지고, 마지막에 0이 주어진다. 각 수는 공백으로 구분된다. 학생 I가 학생 J를 알면 학생 J도 학생 I를 안다.

첫째 줄에 가능한 최소 분할 점수를 출력한다.

둘째 줄에는 모둠의 개수와 각 모둠의 크기를 생년월일이 빠른 모둠부터 공백으로 구분하여 출력한다. 최소 점수를 만드는 분할이 여러 개라면 그중 아무 하나를 출력한다.