시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 173 41 34 23.611%

문제

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

교육원에서는 다음과 같은 방식으로 학생들을 몇 개의 모둠으로 분할하려고 한다. 먼저 학생들의 명단을 생년월일 순서대로 나열한 다음, 나열된 순서에서 연속된 구간에 속한 학생들을 하나의 모둠으로 구성할 것이다. 이 때, 분할을 위한 원칙은 다음과 같다. 각 모둠에 속한 학생들은 서로 아는 사이여야 하고, 다른 모둠에 속한 학생들과는 서로 모르는 사이여야 한다. 그러나 위의 원칙으로 분할하는 것이 불가능한 경우가 많다. 그래서 가능한 위의 원칙을 따르는 방향으로 분할을 수행하기 위해, 분할 점수라는 값을 도입하여 구성된 분할이 얼마나 좋은지를 평가한다. 분할 점수는 다음과 같이 구해진다.

같은 모둠에 속한 학생들 중에서 서로 모르는 학생 쌍에 대해 각각 1점씩 점수를 부여하고, 다른 모둠에 속한 학생들 중에서 서로 아는 사이인 학생 쌍에 대해 각각 1점씩 점수를 부여한다. 

다음 그림은 모둠의 수가 3이고 분할 점수가 5인 분할의 예를 보여준다. 그림에서 검은색 점은 학생을, 점 사이를 연결하는 선은 학생들이 서로 아는 사이임을 나타낸다. 점선으로 표시된 원은 모둠을 나타낸다. 학생들은 생년월일의 순서대로 1번부터 8번까지 번호로 표시되었고, 각 모둠은 A, B, C로 표시되어 있다. 이 예에서는 모둠 A와 모둠 B 사이의 점들을 연결하는 3개의 선이 존재하고, 모둠 B와 모둠 C 사이의 점들을 연결하는 1개의 선이 존재한다. 모둠 A와 모둠 B의 경우, 모둠 내의 모든 점들 쌍에 선이 존재하지만, 모둠 C에는 점 7과 점 8 사이에 선이 존재하지 않는다. 따라서 분할 점수는 3+1+1=5 이다.

아래 그림과 같이 두 개의 모둠으로 분할된 경우에도 분할 점수는 5이다. 

아래 그림과 같이 4개의 모둠으로 분할된 경우에는 분할 점수가 8이다. 

학생들에 대한 정보가 주어질 때, 분할 점수가 최소가 되는 분할을 구하는 프로그램을 작성하시오. 단, 모둠이 한 개만 있는 분할도 존재할 수 있다.

입력

첫째 줄에는 학생들의 수 N이 주어진다. N은 2 이상 3,000 이하이다. 학생들은 1부터 N까지 번호로 구분되고, 번호가 작은 학생은 번호가 큰 학생보다 생년월일이 빠르다. 둘째 줄부터 시작하여 N개의 줄에는 서로 알고 지내는 학생들에 대한 정보가 주어진다. 이들 중 K번째 줄에는 학생 K가 알고 있는 학생들의 번호와 끝을 나타내는 0이 빈칸을 사이에 두고 주어진다(K=1,2,...,N). 학생 번호들은 오름차순으로 주어진다. 학생 I가 학생 J를 알고 있으면, 항상 학생 J도 학생 I를 알고 있다.

출력

첫째 줄에 최적으로 분할한 경우의 분할 점수를 출력하고, 둘째 줄에는 모둠의 개수와 각 모둠의 크기를 빈칸을 사이에 두고 출력한다. 모둠은 생년월일이 빠른 학생들의 모둠부터 출력한다. 만일 분할 점수가 같은 분할이 여러 개 있으면 그 중 하나만 출력한다. 

예제 입력

8
2 3 0
1 3 4 0
1 2 4 5 0
2 3 5 0
3 4 6 0
5 7 8 0
6 0
6 0

예제 출력

5
3 3 2 3

힌트