Порядок доения (Золото)
n коров фермера Джона, пронумерованных 1..n, разработали социальную иерархию, в соответствии с которой ФД доит их каждое утро.
ФД сделал m наблюдений об этой структуре. Каждое наблюдение - упорядоченный список некоторых из его коров, указывающий что их нужно доить именно в таком порядке. Например список 2 5 1 означает, он должен подоить корову 2, некоторое время спустя - корову 5 и некоторое время после - корову 1.
Наблюдения ФД приоритезированы, поэтому его цель - максимизировать значение X так, чтобы выполнились условия первых X наблюдений. Если несколько порядков дойки могут удовлетворять X наблюдениям, он выбирает тот, в котором корова с меньшим номером доится раньше. Иными словами, если несколько порядков дойки удовлетворяют этим условиям, ФД выбирает лексикографически наименьший. Порядок x является лексикографически меньшим, чем порядок y, если для некоторого j, x[i] = y[i] для всех i < j и x[j] < y[j] (другими словами два порядка идентичны до некоторой точки, в которой x меньше чем y).
Помогите ФД определить наилучший порядок дойки его коров.
Входные данные
Первая строка содержит числа n (1 ≤ n ≤ 10^5) и m (1 ≤ m ≤ 50000). Каждая из следующих m строк описывает одно наблюдение. Строка i + 1 описывает наблюдение i и начинается с количества коров m[i] в этом наблюдении, за которым следует список из m[i] целых чисел, определяющих порядок коров в этом наблюдении. Сумма m[i] не превышает 200000.
Выходные данные
Выведите n целых чисел дающих перестановку чисел of 1..n, содержащую порядок в котором ФД должен доить своих коров.
Пример
Здесь у ФД 4 коровы и он должен доить корову 1 перед коровой 2 и корову 2 перед коровой 3 (первое наблюдение), также он должен доить корову 4 перед коровой 2 (второе наблюдение), и корову 3 перед коровой 4 и корову 4 перед коровой 1 (третье наблюдение). Первые два наблюдения можно удовлетворить одновременно, но с третьим не получается поскольку нужно доить корову 1 перед коровой 3 и корову 3 перед коровой 1.
Это означает, что есть два возможных порядка: 1 4 2 3 и 4 1 2 3, из которых первый - лексикографически наименьший.