Có \(N\) học sinh và \(N\) loại đồ ăn nhẹ, đều được đánh số từ \(1\) đến \(N\). Học sinh \(i\) thích \(C_i\) loại có chỉ số \(A_{i,1},\ldots,A_{i,C_i}\). Ban đầu mỗi loại đồ ăn có đúng một chiếc.

Đưa các học sinh vào phòng theo một thứ tự. Khi vào, một học sinh lấy tất cả đồ ăn mà mình thích và còn lại trong phòng. Hãy quyết định liệu có thể chọn thứ tự sao cho mọi học sinh lấy đúng một đồ ăn hay không. Nếu có, hãy in một thứ tự như vậy.

Dữ liệu vào

• Dòng đầu chứa \(N\).
• \(N\) dòng tiếp theo: dòng \(i\) chứa \(C_i\) rồi đến \(C_i\) số \(A_{i,j}\).

Dữ liệu ra

In -1 nếu không thể. Ngược lại in một hoán vị \(P_1,\ldots,P_N\) sao cho khi học sinh vào theo thứ tự đó, mỗi người lấy đúng một đồ ăn.

Ràng buộc

• \(1 \le N \le 200000\), \(1 \le C_i \le N\).
• \(1 \le A_{i,j} \le N\).
• \(\sum C_i \le 500000\); các đồ ăn mà cùng một học sinh thích là khác nhau.

Phân nhóm

• Nhóm 1 (6 điểm): \(C_i = 1\) với mọi \(i\).
• Nhóm 2 (11 điểm): nếu tồn tại thứ tự hợp lệ thì thứ tự \(1,2,\ldots,N\) cũng hợp lệ.
• Nhóm 3 (8 điểm): \(N \le 5\).
• Nhóm 4 (12 điểm): \(N \le 18\).
• Nhóm 5 (18 điểm): \(N \le 300\).
• Nhóm 6 (20 điểm): \(N \le 5000\).
• Nhóm 7 (25 điểm): Không có ràng buộc bổ sung.

Ví dụ

3
2 1 2
2 2 3
1 2

3 1 2

Theo thứ tự này, học sinh \(3\) lấy đồ ăn \(2\), học sinh \(1\) lấy đồ ăn \(1\), rồi học sinh \(2\) lấy đồ ăn \(3\); vì vậy mỗi người lấy đúng một món.

2
2 1 2
2 1 2

-1

4
1 3
1 2
3 4 2 3
2 1 2

1 2 3 4

Nguồn

KOI 2026 Round 2, problem Snack Distribution. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.