시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 50 34 28 73.684%

문제

홍은 유치원에 근무하는 선생님은 총 세 명이다. 새 학기가 시작될 때, 선생님은 학생들의 반을 나눠야 한다.

선생님은 학생들의 친구 관계를 반 배정에 포함시킨다. 모든 아이들은 자신이 좋아하는 순서대로 다른 아이의 이름을 적어서 선생님께 제출했다. 좋아하는 순서는 같은 반이 되길 원하는 순서와 같다.

반의 크기가 같지 않아도 상관없다. 유치원에는 매년 새 학생이 들어오기 때문에, 그 아이들로 반을 채우면 된다. 하지만, 선생님은 작년에 맡았던 학생을 절대로 다시 맡지 않을 것이다.

뛰어난 컴퓨터 프로그래머 출신인 김상근 선생님은 모든 학생을 작년과 다른 반에 배정하면서, 각 반에 있는 모든 학생이 그 반에 속하는 학생이 제출한 순서에서 모두 상위 T위 안에 드는 방법을 찾으려고 한다. 이 때, T는 가능한 작아야 한다.

입력

첫째 줄에 학생의 수 n ≤ 200 이 주어진다. 아이들의 번호는 1번부터 n번이다.

다음 n개 줄에는 각 학생들의 정보가 주어진다. 첫 번째 숫자는 작년 선생님을 나타내며 0, 1, 2중 하나이다. 다음 n-1개 숫자는 {1, 2, ..., i-1, i+1, ..., n} 이며, 주어지는 순서대로 i번 학생이 좋아하는 순서이다.

출력

가장 작은 음이 아닌 정수 T를 출력한다. T는 다음 조건을 만족해야 한다.

  • 작년과 같은 선생님의 반에 속하는 학생이 없어야 한다.
  • 반에 속하는 모든 학생은 학생들이 좋아하는 순서에서 상위 T위 안에 있어야 한다.

예제 입력

6
0 2 3 4 5 6
0 1 3 4 5 6
1 6 5 4 2 1
2 6 5 3 2 1
1 1 2 3 4 6
2 1 2 3 4 5

예제 출력

4

예제 입력 2

3
0 2 3
1 1 3
2 1 2

예제 출력 2

0

힌트