测试数据来自 system/1893

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　H老师的 \(N\) 名学生们每天都要排队就餐（编号为 \(1..N\) ），但是他发现，小朋友们排队顺序基本会遵循相对固定的习惯。

　　为研究这个习惯，H老师总计进行了 \(M\) 次的观察。每个观察结果都是某些学生的一个有序序列，表示这些学生基本会以相同的顺序进行排队。比方说，如果H老师的一次观察结果是序列 2、5、1，则在队列中，学生5 在学生2 之后，学生1 在学生 5 之后。

　　H老师的观察结果是按顺序记录的，所以他的目标是最大化 \(K\) 的值，使得他的排队顺序能够符合前 \(K\) 个观察结果描述的状态。当多种排队顺序都能符合前 \(K\) 个记录，H老师需要找到一个字典序较小的排队序列。

【输入格式】

　　第一行包含 \(N\) 和 \(M\)。
　　接下来的 \(M\) 行，每行描述了一个观察记录。
　　第 \(i+1\) 行描述了第 \(i\) 条记录，第一个数是观察结果中的学生数量 \(m_i\)，后面是一列 \(m_i\) 个整数，给出这次观察中学生的顺序。

【输出格式】

　　输出 \(N\) 个空格分隔的整数，给出一个 \(1…N\) 的排列，为学生们的排队顺序。

【输入输出样例】

　Input

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

　Output

1 4 2 3

【输入输出样例说明】

　　这里，H老师有四个学生，他有三条观察记录：
　　第一条记录：排队顺序应该是学生1在学生2之前、学生2在学生3之前；
　　第二条记录：排队顺序应该是学生4在学生2之前；
　　第三条记录：排队顺序应该是学生3在学生4之前、学生4在学生1之前。
　　前两个观察结果可以同时被满足，但是H老师不能同时满足所有的规则，因为这样的话会要求学生1在学生3之前，同时学生3在学生1之前。这意味着总共有两种可能的排队顺序：1 4 2 3和4 1 2 3，第一种是字典序较小的。

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤100000\)，所有 \(m_i\) 的和至多为 200,000。

【来源】

　　Mr.he