시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 71 49 41 74.545%

문제

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

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

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

뛰어난 컴퓨터 프로그래머 출신인 김상근 선생님은 모든 학생을 작년과 다른 반에 배정하면서, 각 반에 있는 모든 학생이 그 반에 속하는 학생이 제출한 순서에서 모두 상위 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+XHJcblxyXG48cD5cdWI2ZjBcdWM1YjRcdWIwOWMgXHVjZWY0XHVkNGU4XHVkMTMwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmEzOCBcdWNkOWNcdWMyZTBcdWM3NzggXHVhZTQwXHVjMGMxXHVhZGZjIFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHVjNzQ0IFx1Yzc5MVx1YjE0NFx1YWNmYyBcdWIyZTRcdWI5NzggXHViYzE4XHVjNWQwIFx1YmMzMFx1YzgxNVx1ZDU1OFx1YmE3NFx1YzExYywgXHVhYzAxIFx1YmMxOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWFkZjggXHViYzE4XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjODFjXHVjZDljXHVkNTVjIFx1YzIxY1x1YzExY1x1YzVkMFx1YzExYyBcdWJhYThcdWI0NTAgXHVjMGMxXHVjNzA0IFRcdWM3MDQgXHVjNTQ4XHVjNWQwIFx1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBUXHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM3OTFcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4IG4gJmxlOyAyMDAgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIG5cdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1Yzc5MVx1YjE0NCBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwIDAsIDEsIDJcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgbi0xXHVhYzFjIFx1YzIyYlx1Yzc5MFx1YjI5NCB7MSwgMiwgLi4uLCBpLTEsIGkrMSwgLi4uLCBufSBcdWM3NzRcdWJhNzAsIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgaVx1YmM4OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4IFRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBUXHViMjk0IFx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3OTFcdWIxNDRcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc1OCBcdWJjMThcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM1YzZcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJjMThcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWM1ZDBcdWMxMWMgXHVjMGMxXHVjNzA0IFRcdWM3MDQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS2luZGVyZ2FydGVuIiwiZGVzY3JpcHRpb24iOiI8cD5FdmVyeSB5ZWFyIHRoZSB0aHJlZSBmcmllbmRseSB0ZWFjaGVycyBhdCB0aGUga2luZGVyZ2FydGVuIGxldCB0aGVpciBjbGFzc2VzJnJzcXVvOyBraWRzIGNoYW5nZSBjbGFzc2VzIHRvIGZvcm0gdGhyZWUgbmV3IG9uZXMuIFNvbWUga2lkcywgb2YgY291cnNlLCBhcmUgb2xkIGVub3VnaCB0byBsZWF2ZSwgYnV0IHRob3NlIHdobyBzdGF5IGZvciBhbm90aGVyIHllYXIgYXJlIHJlYXJyYW5nZWQgYW1vbmcgdGhlIHRocmVlIHRlYWNoZXJzLjxcL3A+XHJcblxyXG48cD5UaGUgdGVhY2hlcnMgZXZlbiBsZXQgdGhlIGtpZHMgaGF2ZSB0aGVpciBzYXkgaW4gdGhlIHByb2Nlc3MuIEFzIGZyaWVuZHNoaXAgYm90aCBjb21lcyBhbmQgZ29lcyBoYXN0aWx5IGluIHlvdW5nIHllYXJzLCBlYWNoIGtpZCBYIHJhbmtzIGV2ZXJ5IG90aGVyIGtpZCBZIGFjY29yZGluZyB0byBob3cgZ2xhZCBYIHdvdWxkIGJlIHRvIGhhdmUgWSBpbiBoZXIgbmV3IGNsYXNzLiBJbiBmYWN0LCBYIHByb2R1Y2VzIGEgcHJlZmVyZW5jZSBsaXN0IGdpdmluZyBhIHRvdGFsIG9yZGVyIG9mIHRoZSBvdGhlciBraWRzLCBpLmUuIHRoZXJlIGFyZSBubyBzdWNoIHRoaW5ncyBhcyB0aWVzIC0ga2lkcyBzaGUgd291bGQgYmUgZXF1YWxseSBnbGFkIHRvIGhhdmUgYXMgY2xhc3MgbWF0ZXMuPFwvcD5cclxuXHJcbjxwPlRoZSB0aHJlZSB0ZWFjaGVycyBkbyBub3QgbWluZCBpZiB0aGUgbmV3IGNsYXNzZXMgZm9ybWVkIGFyZSB1bmJhbGFuY2VkIGluIHNpemUsIHNpbmNlIHRoZXkgXHVmYjAxbGwgdXAgdGhlaXIgY2xhc3NlcyB3aXRoIG5ldyBraWRzIGFib3V0IHRvIHN0YXJ0IHRoZWlyIFx1ZmIwMXJzdCB5ZWFyIGF0IHRoZSBraW5kZXJnYXJ0ZW4uIFRoZXkgZG8sIGhvd2V2ZXIsIHdhbnQgYWxsIHRoZSBraWRzIGluIHRoZWlyIG93biBuZXcgY2xhc3MgdG8gYmUgZGlmZmVyZW50IGZyb20gbGFzdCB5ZWFyLCBzaW5jZSBldmVuIGEgdGVhY2hlciBuZWVkcyBhIGJyZWFrIGFmdGVyIGEgd2hvbGUgeWVhciB3aXRoIHRoZSBzYW1lIGtpZHMuIFRoZXkgZGVjaWRlIHRoYXQgYSBiZXN0IHBhcnRpdGlvbiBpbnRvIHRocmVlIGNsYXNzZXMgdW5kZXIgdGhlc2UgcHJlbWlzZXMgaXMgb25lIHdoZXJlIG5vIGtpZCBpcyBpbiB0aGUgc2FtZSBjbGFzcyBhcyBhIGtpZCBub3QgbGlzdGVkIGFtb25nIHRoZSB0b3AgVCBlbnRyaWVzIG9uIHRoZWlyIHByZWZlcmVuY2UgbGlzdCwgZm9yIFQgYXMgc21hbGwgYXMgcG9zc2libGUuIE5vdGUgdGhhdCB0aGUga2lkcyBpbiBhIG5ldyBjbGFzcyBtYXkgdmVyeSB3ZWxsIGJlIHRoZSBzYW1lIGFzIGluIGFuIG9sZCBvbmUsIGJ1dCB0aGVuIHdpdGggYSBuZXcgdGVhY2hlciE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgbiAmbGU7IDIwMCBnaXZpbmcgdGhlIG51bWJlciBvZiBraWRzIHRvIGJlIHJlYXJyYW5nZWQgYXQgdGhlIGtpbmRlcmdhcmRlbi4gVGhlIGtpZHMgYXJlIG51bWJlcmVkIDEgdGhyb3VnaCBuLjxcL3A+XHJcblxyXG48cD5UaGVuIGZvbGxvdyBuIGxpbmVzIGRlc2NyaWJpbmcgdGhlIGtpZHMuIFRoZSBpLXRoIHJvdyBcdWZiMDFyc3QgY29udGFpbnMgdGhlIGlkZW50aVx1ZmIwMWVyIG9mIHRoZWlyIGN1cnJlbnQgY2xhc3MmcnNxdW87IHRlYWNoZXIgKGFuIGludGVnZXIgMCwgMSwgb3IgMiksIGFuZCBuZXh0IHRoZSBuICZtaW51czsgMSBpbnRlZ2VycyB7MSwyLDMsIC4uLiAsIGkgJm1pbnVzOyAxLCBpICsgMSwgLi4uICwgbn0gaW4gc29tZSBvcmRlciwgZGVzY3JpYmluZyB0aGUgY2xhc3MgbWF0ZSBwcmVmZXJlbmNlIGxpc3Qgb2YgdGhlIGktdGgga2lkLCBpbiBkZXNjZW5kaW5nIG9yZGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBzbWFsbGVzdCBub24tbmVnYXRpdmUgaW50ZWdlciBULCBzdWNoIHRoYXQgdGhlcmUgaXMgYSBwYXJ0aXRpb25pbmcgb2YgdGhlIGtpZHMgaW4gdGhyZWUgbmV3IGNsYXNzZXMgc3VjaCB0aGF0PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Tm8ga2lkIGhhcyB0aGUgc2FtZSB0ZWFjaGVyIGFzIGluIHRoZWlyIGN1cnJlbnQgY2xhc3MsIGFuZDxcL2xpPlxyXG5cdDxsaT5hbGwga2lkcyZyc3F1bzsgY2xhc3MgbWF0ZXMgYXJlIGFtb25nIHRoZSB0b3AgVCBwbGFjZXMgb2YgdGhlaXIgcHJlZmVyZW5jZSBsaXN0cywgcmVzcGVjdGl2ZWx5PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=