Một nhóm phi hành gia được tham gia một khóa huấn luyện trên tàu vũ trũ ngoài không gian. Trong suốt quá trình huấn luyện, mỗi phi hành gia được khám phá một lộ trình từ phòng trên cùng đến phòng dưới cùng của tàu vũ trụ. Phi hành gia chỉ có thể di chuyển liên tục từ phòng này qua phòng khác bằng cách đi qua các hành lang. Mặt khác, mỗi phi hành gia phải xuất phát từ những hành lang khác nhau khi rời khỏi phòng trên cùng và phải vào phòng dưới cùng bằng các hành lang khác nhau.

Cho biết tàu vũ trũ có \(n\) phòng, các phòng được đánh số thứ tự từ 1 đến \(n\), phòng trên cùng là 1, phòng dưới cùng là \(n\). Hãy cho biết có tối đa bao nhiêu phi hành gia xuất phát cùng một lúc.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (2 \leq n \leq 200)\)

+\(n - 1\) dòng tiếp theo, dòng thứ \(i\) cho biết:

• Số đầu tiên là \(m\) cho là số lượng phòng có hành lang xuất phát từ phòng \(i\)

• \(m\) số tiếp theo mỗi số \(x\) cho biết có hành lang từ phòng \(i\) đến phòng \(x\ (i < x \leq n)\)

Kết quả:

Một số nguyên duy nhất là kết quả bài toán

Ví dụ:

Solution

Chuyển bài toán về luồng cực đại trên mạng với đỉnh phát là 1, đỉnh thu là \(n\).

Ví mỗi hành lang xuất phát từ 1 và kết thúc tại \(n\) chỉ cho một phi hành gia đi qua nên đặt trọng số là 1, các hành lang còn lại có trọng số INT_MAX

Việc còn lại là tìm luồng cực đại trên mạng.