Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Tại nhà trẻ Super Kid, 3 giáo viên vẫn tận tình chăm sóc 3 lớp trẻ mẫu giáo của mình. Mỗi năm, sẽ lại có những đứa trẻ lớn đi học tiểu học, và những đứa trẻ nhỏ mới sẽ cập bến nhà trẻ này. Năm nay, nhà trẻ còn lại N đứa trẻ, các giáo viên đang nghĩ cách để xếp lại lớp cho chúng.

Các giáo viên muốn các đứa trẻ này được thay đổi giáo viên. Và họ không muốn những đứa trẻ này xa rời những người bạn thân của chúng. Họ đã yêu cầu những đứa trẻ liệt kê ra danh sách những người bạn muốn được học cùng ở năm tới, theo thứ tự độ ưu tiên giảm dần.

3 giáo viên không quan tâm đến việc lớp học sẽ bị mất cân bằng về số lượng, họ sẽ bổ sung những đứa trẻ nhỏ mới khi năm học mới bắt đầu. Họ đã tìm ra một cách sắp xếp tốt nhất, sao cho các đứa trẻ sẽ có giáo viên mới và bạn trong lớp của mỗi đứa trẻ là những người bạn năm trong top T của danh sách mà chúng đã gửi cho các giáo viên.

Nhiệm vụ của bạn là hãy tìm số nguyên T nhỏ nhất, sao cho các giáo viên có thể sắp xếp lại được lớp học mới theo đúng nguyên tắc của mình:

• Không có đứa trẻ nào học lại giáo viên cũ.
• Các đứa trẻ trong cùng một lớp phải xuất hiện trong top T của danh sách mà mỗi đứa trẻ gửi đi.

Input

Dòng đầu tiên chứa 1 số nguyên dương N <=200, là số đứa trẻ còn lại ở nhà trẻ. Chúng được đánh số từ 1 tới N.

N dòng sau miêu tả những đứa trẻ . Dòng thứ i bao gồm: số đầu tiên là lớp học cũ (0,1 và 2), N-1 số nguyên tiếp theo là một hoán vị (không có số i) biểu thị danh sách ưu tiên của đứa trẻ thứ i theo thứ tự giảm dần.

Output

In ra số nguyên T nhỏ nhất thỏa mãn yêu cầu của đề bài.

Example

Test 1:

Input:

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

Output:

4

Giải thích test 1:

Danh sách lớp cũ:

Lớp 0: 1,2

Lớp 1: 3, 5

Lớp 2: 4, 6

Một trong những cách xếp lớp mới với Tmin = 4 là:

Lớp 0: 4, 6

Lớp 1: 1, 2

Lớp 2: 3, 5

Test 2:

Input:

3
0 2 3
1 1 3
2 1 2

Output:

0