시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 64 45 36 76.596%

문제

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

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

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

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

입력

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

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

출력

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

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

예제 입력 1

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

예제 출력 1

4

예제 입력 2

3
0 2 3
1 1 3
2 1 2

예제 출력 2

0

힌트

W3sicHJvYmxlbV9pZCI6IjUwMDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWNlNThcdWM2ZDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDY0ZFx1Yzc0MCBcdWM3MjBcdWNlNThcdWM2ZDBcdWM1ZDAgXHVhZGZjXHViYjM0XHVkNTU4XHViMjk0IFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWNkMWQgXHVjMTM4IFx1YmE4NVx1Yzc3NFx1YjJlNC4gXHVjMGM4IFx1ZDU1OVx1YWUzMFx1YWMwMCBcdWMyZGNcdWM3OTFcdWI0MjAgXHViNTRjLCBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YmMxOFx1Yzc0NCBcdWIwOThcdWIyMjBcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzRcdWI5N2MgXHViYzE4IFx1YmMzMFx1YzgxNVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWMyZGNcdWQwYThcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMmU0XHViOTc4IFx1YzU0NFx1Yzc3NFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDQgXHVjODAxXHVjNWI0XHVjMTFjIFx1YzEyMFx1YzBkZFx1YjJkOFx1YWVkOCBcdWM4MWNcdWNkOWNcdWQ1ODhcdWIyZTQuIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YmMxOFx1Yzc3NCBcdWI0MThcdWFlMzggXHVjNmQwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMxOFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVhYzE5XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuIFx1YzcyMFx1Y2U1OFx1YzZkMFx1YzVkMFx1YjI5NCBcdWI5ZTRcdWIxNDQgXHVjMGM4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFkZjggXHVjNTQ0XHVjNzc0XHViNGU0XHViODVjIFx1YmMxOFx1Yzc0NCBcdWNjNDRcdWM2YjBcdWJhNzQgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWM3OTFcdWIxNDRcdWM1ZDAgXHViOWUxXHVjNTU4XHViMzU4IFx1ZDU1OVx1YzBkZFx1Yzc0NCBcdWM4MDhcdWIzMDBcdWI4NWMgXHViMmU0XHVjMmRjIFx1YjllMVx1YzljMCBcdWM1NGFcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI2ZjBcdWM1YjRcdWIwOWMgXHVjZWY0XHVkNGU4XHVkMTMwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmEzOCBcdWNkOWNcdWMyZTBcdWM3NzggXHVhZTQwXHVjMGMxXHVhZGZjIFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHVjNzQ0IFx1Yzc5MVx1YjE0NFx1YWNmYyBcdWIyZTRcdWI5NzggXHViYzE4XHVjNWQwIFx1YmMzMFx1YzgxNVx1ZDU1OFx1YmE3NFx1YzExYywgXHVhYzAxIFx1YmMxOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWFkZjggXHViYzE4XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjODFjXHVjZDljXHVkNTVjIFx1YzIxY1x1YzExY1x1YzVkMFx1YzExYyBcdWJhYThcdWI0NTAgXHVjMGMxXHVjNzA0IFRcdWM3MDQgXHVjNTQ4XHVjNWQwIFx1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgVFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzkxXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCBuICZsZTsgMjAwIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBuXHViYzg4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM3OTFcdWIxNDQgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCAwLCAxLCAyXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIG4tMVx1YWMxYyBcdWMyMmJcdWM3OTBcdWIyOTQgezEsIDIsIC4uLiwgaS0xLCBpKzEsIC4uLiwgbn0gXHVjNzc0XHViYTcwLCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIGlcdWJjODggXHVkNTU5XHVjMGRkXHVjNzc0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCBUXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gVFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNzkxXHViMTQ0XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NTggXHViYzE4XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNWM2XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYzE4XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHVjNzQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHVjNWQwXHVjMTFjIFx1YzBjMVx1YzcwNCBUXHVjNzA0IFx1YzU0OFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTAwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktpbmRlcmdhcnRlbiIsImRlc2NyaXB0aW9uIjoiPHA+RXZlcnkgeWVhciB0aGUgdGhyZWUgZnJpZW5kbHkgdGVhY2hlcnMgYXQgdGhlIGtpbmRlcmdhcnRlbiBsZXQgdGhlaXIgY2xhc3NlcyZyc3F1bzsga2lkcyBjaGFuZ2UgY2xhc3NlcyB0byBmb3JtIHRocmVlIG5ldyBvbmVzLiBTb21lIGtpZHMsIG9mIGNvdXJzZSwgYXJlIG9sZCBlbm91Z2ggdG8gbGVhdmUsIGJ1dCB0aG9zZSB3aG8gc3RheSBmb3IgYW5vdGhlciB5ZWFyIGFyZSByZWFycmFuZ2VkIGFtb25nIHRoZSB0aHJlZSB0ZWFjaGVycy48XC9wPlxyXG5cclxuPHA+VGhlIHRlYWNoZXJzIGV2ZW4gbGV0IHRoZSBraWRzIGhhdmUgdGhlaXIgc2F5IGluIHRoZSBwcm9jZXNzLiBBcyBmcmllbmRzaGlwIGJvdGggY29tZXMgYW5kIGdvZXMgaGFzdGlseSBpbiB5b3VuZyB5ZWFycywgZWFjaCBraWQgWCByYW5rcyBldmVyeSBvdGhlciBraWQgWSBhY2NvcmRpbmcgdG8gaG93IGdsYWQgWCB3b3VsZCBiZSB0byBoYXZlIFkgaW4gaGVyIG5ldyBjbGFzcy4gSW4gZmFjdCwgWCBwcm9kdWNlcyBhIHByZWZlcmVuY2UgbGlzdCBnaXZpbmcgYSB0b3RhbCBvcmRlciBvZiB0aGUgb3RoZXIga2lkcywgaS5lLiB0aGVyZSBhcmUgbm8gc3VjaCB0aGluZ3MgYXMgdGllcyAtIGtpZHMgc2hlIHdvdWxkIGJlIGVxdWFsbHkgZ2xhZCB0byBoYXZlIGFzIGNsYXNzIG1hdGVzLjxcL3A+XHJcblxyXG48cD5UaGUgdGhyZWUgdGVhY2hlcnMgZG8gbm90IG1pbmQgaWYgdGhlIG5ldyBjbGFzc2VzIGZvcm1lZCBhcmUgdW5iYWxhbmNlZCBpbiBzaXplLCBzaW5jZSB0aGV5IFx1ZmIwMWxsIHVwIHRoZWlyIGNsYXNzZXMgd2l0aCBuZXcga2lkcyBhYm91dCB0byBzdGFydCB0aGVpciBcdWZiMDFyc3QgeWVhciBhdCB0aGUga2luZGVyZ2FydGVuLiBUaGV5IGRvLCBob3dldmVyLCB3YW50IGFsbCB0aGUga2lkcyBpbiB0aGVpciBvd24gbmV3IGNsYXNzIHRvIGJlIGRpZmZlcmVudCBmcm9tIGxhc3QgeWVhciwgc2luY2UgZXZlbiBhIHRlYWNoZXIgbmVlZHMgYSBicmVhayBhZnRlciBhIHdob2xlIHllYXIgd2l0aCB0aGUgc2FtZSBraWRzLiBUaGV5IGRlY2lkZSB0aGF0IGEgYmVzdCBwYXJ0aXRpb24gaW50byB0aHJlZSBjbGFzc2VzIHVuZGVyIHRoZXNlIHByZW1pc2VzIGlzIG9uZSB3aGVyZSBubyBraWQgaXMgaW4gdGhlIHNhbWUgY2xhc3MgYXMgYSBraWQgbm90IGxpc3RlZCBhbW9uZyB0aGUgdG9wIFQgZW50cmllcyBvbiB0aGVpciBwcmVmZXJlbmNlIGxpc3QsIGZvciBUIGFzIHNtYWxsIGFzIHBvc3NpYmxlLiBOb3RlIHRoYXQgdGhlIGtpZHMgaW4gYSBuZXcgY2xhc3MgbWF5IHZlcnkgd2VsbCBiZSB0aGUgc2FtZSBhcyBpbiBhbiBvbGQgb25lLCBidXQgdGhlbiB3aXRoIGEgbmV3IHRlYWNoZXIhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIG4gJmxlOyAyMDAgZ2l2aW5nIHRoZSBudW1iZXIgb2Yga2lkcyB0byBiZSByZWFycmFuZ2VkIGF0IHRoZSBraW5kZXJnYXJkZW4uIFRoZSBraWRzIGFyZSBudW1iZXJlZCAxIHRocm91Z2ggbi48XC9wPlxyXG5cclxuPHA+VGhlbiBmb2xsb3cgbiBsaW5lcyBkZXNjcmliaW5nIHRoZSBraWRzLiBUaGUgaS10aCByb3cgXHVmYjAxcnN0IGNvbnRhaW5zIHRoZSBpZGVudGlcdWZiMDFlciBvZiB0aGVpciBjdXJyZW50IGNsYXNzJnJzcXVvOyB0ZWFjaGVyIChhbiBpbnRlZ2VyIDAsIDEsIG9yIDIpLCBhbmQgbmV4dCB0aGUgbiAmbWludXM7IDEgaW50ZWdlcnMgezEsMiwzLCAuLi4gLCBpICZtaW51czsgMSwgaSArIDEsIC4uLiAsIG59IGluIHNvbWUgb3JkZXIsIGRlc2NyaWJpbmcgdGhlIGNsYXNzIG1hdGUgcHJlZmVyZW5jZSBsaXN0IG9mIHRoZSBpLXRoIGtpZCwgaW4gZGVzY2VuZGluZyBvcmRlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgc21hbGxlc3Qgbm9uLW5lZ2F0aXZlIGludGVnZXIgVCwgc3VjaCB0aGF0IHRoZXJlIGlzIGEgcGFydGl0aW9uaW5nIG9mIHRoZSBraWRzIGluIHRocmVlIG5ldyBjbGFzc2VzIHN1Y2ggdGhhdDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk5vIGtpZCBoYXMgdGhlIHNhbWUgdGVhY2hlciBhcyBpbiB0aGVpciBjdXJyZW50IGNsYXNzLCBhbmQ8XC9saT5cclxuXHQ8bGk+YWxsIGtpZHMmcnNxdW87IGNsYXNzIG1hdGVzIGFyZSBhbW9uZyB0aGUgdG9wIFQgcGxhY2VzIG9mIHRoZWlyIHByZWZlcmVuY2UgbGlzdHMsIHJlc3BlY3RpdmVseTxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d