\(N\) cô bò của bác nông dân John (\(1 \leq N \leq 10^5\)), như thường lệ được đánh số từ \(1 \ldots N\), tình cờ có quá nhiều thời gian rảnh. Vì vậy, chúng đã xây dựng một hệ thống thứ bậc xã hội phức tạp liên quan đến thứ tự bác nông dân John vắt sữa chúng vào mỗi buổi sáng.

Sau nhiều tuần nghiên cứu, bác nông dân John đã ghi nhận \(M\) quan sát về cấu trúc xã hội của đàn bò (\(1 \leq M \leq 50\,000\)). Mỗi quan sát là một danh sách có thứ tự gồm một số cô bò, cho biết những cô bò này phải được vắt sữa theo đúng thứ tự xuất hiện trong danh sách. Ví dụ, nếu một trong các quan sát của bác nông dân John là danh sách 2, 5, 1, thì ông phải vắt sữa bò 2 trước bò 5 vào một thời điểm nào đó, rồi vắt sữa bò 5 trước bò 1 vào một thời điểm nào đó.

Các quan sát của bác nông dân John được xếp theo mức độ ưu tiên, nên mục tiêu của ông là tối đa hóa giá trị \(X\) sao cho thứ tự vắt sữa thỏa mãn các điều kiện trong \(X\) quan sát đầu tiên. Nếu có nhiều thứ tự vắt sữa thỏa mãn \(X\) điều kiện đầu tiên này, bác nông dân John tin rằng theo một truyền thống lâu đời, những cô bò có số nhỏ hơn có thứ bậc cao hơn những cô bò có số lớn hơn, nên ông muốn vắt sữa những cô bò mang số nhỏ hơn trước. Nói chính xác hơn, nếu có nhiều thứ tự vắt sữa thỏa mãn các điều kiện, ông muốn dùng thứ tự nhỏ nhất theo thứ tự từ điển. Một thứ tự \(x\) nhỏ hơn theo thứ tự từ điển so với một thứ tự \(y\) nếu tồn tại một vị trí \(j\) sao cho \(x_i = y_i\) với mọi \(i < j\) và \(x_j < y_j\); nói cách khác, hai thứ tự giống hệt nhau cho tới một vị trí nhất định, và tại đó \(x\) nhỏ hơn \(y\).

Hãy giúp bác nông dân John xác định thứ tự tốt nhất để vắt sữa đàn bò.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một quan sát. Dòng \(i+1\) mô tả quan sát \(i\), bắt đầu bằng số lượng bò \(m_i\) được liệt kê trong quan sát, sau đó là danh sách \(m_i\) số nguyên cho biết thứ tự của các cô bò trong quan sát. Tổng tất cả các giá trị \(m_i\) không vượt quá \(200\,000\).

Dữ liệu ra

In ra \(N\) số nguyên cách nhau bởi dấu cách, tạo thành một hoán vị của \(1 \ldots N\), cho biết thứ tự bác nông dân John nên vắt sữa đàn bò.

Ví dụ

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

1 4 2 3

Nguồn

USACO 2018 US Open Contest, Gold — Milking Order

Tác giả bài toán: Jay Leeds.