题目描述

有 $N$ 个发射台，编号为 $1$ 到 $N$。现有 $M$ 条按优先级从高到低排列的记录。每条记录给出若干个互不相同的发射台，并要求它们按照记录中的先后顺序依次激活。

需要从第 $1$ 条记录开始，选择一个尽可能长的连续前缀，使这些记录的要求能够同时满足。在满足这个最长前缀的所有激活顺序中，输出字典序最小的一个。

激活顺序必须是 $1$ 到 $N$ 的一个排列。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行先包含一个整数 $C_i$，再包含 $C_i$ 个互不相同的整数，按顺序表示第 $i$ 条记录中的发射台。

输出格式

输出 $N$ 个整数，表示字典序最小的合法激活顺序，相邻整数之间用一个空格分隔。

样例

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

1 4 2 3

数据范围与提示

• 对于 $30\%$ 的数据，$1 \le N,M \le 10$
• 对于 $50\%$ 的数据，$1 \le N \le 10^4$，$1 \le M \le 5\times10^3$，$1 \le C_i \le 10$
• 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le M \le 5\times10^4$，$\sum C_i \le 2\times10^5$
• 每条记录中的编号均在 $1$ 到 $N$ 之间，并且互不相同