解决了之前的问题后，DoubleDog 们陷入了难题：如何让 SinglePig 相信自己也曾经是 dog 中的一员？DoubleDog 们希望能够找到族谱来证明这一点。

不幸的是，可能是由于一代代传下来造成的微小偏差，DoubleDog 们收集到了 $k$ 个不同版本的族谱，其中第 $i$ 个版本的族谱被 $w_i$ 只 DoubleDog 认同。同时由于一些原因，不存在两个集合$S,T\subseteq \{1,\cdots ,k\}$, $S\ne T$ 满足 $\sum _{x\in S}{w}_x=\sum _{y\in T}{w}_y$。

DoubleDog 的族谱是一个恰有 $n$ 个叶子的带标号的有根树，其中 $1\sim n$ 为叶子节点，每个叶子代表了一个dog家族。每个非叶子节点代表一个老家族，它的子树中的所有dog家族都是由它繁衍、分化产生的，可以发现每个老家族唯一对应一个集合$S\subseteq \{1,\cdots ,n\}$。此时我们说老家族$S$在第$i$个族谱里出现了。

对于一个老家族 $S$ 来说，我们定义其认同度为所有$S$出现过的族谱树$i$的 $w_i$ 之和。DoubleDog 将所有 $2^n$ 个可能的老家族中，在任意一个族谱中出现过的老家族按照认同度为第一关键字，从大到小排序，如果有相同认同度的老家族，按照任意顺序排列。

随后尝试选出一种字典序最大的族谱树。（显然有些老家族不能同时出现在一棵族谱树里，现在要在不产生矛盾的情况下，使得一棵族谱树的字典序尽量大。）定义一个族谱树表示的字符串为一个长度为在任一族谱树中出现过的老家族个数的01字符串，当第 $i$ 个老家族（按照之前排序的结果标号）出现在族谱树中时第 $i$ 位的值为 $1$，否则为 $0$。一个族谱树集合比另一个族谱树集合字典序大当且仅当其表示的字符串的字典序更大。

可以证明，在以上条件下，最终选出的族谱树中出现的老家族的集合是唯一的。

你能帮助 DoubleDog 求出这样的族谱树吗？

输入格式

第一行两个整数 $n$ 与 $k$。

接下来一行 $k$ 个数，表示认同第 $i$ 个版本的族谱的 DoubleDog 数目。

接下来描述这 $k$ 个版本的族谱。对于每个版本的族谱，输入的第一行是族谱树上的节点数 $m>n$，接下来的一行包括 $m$ 个正整数，其中第 $i$ 个数表示点 $i$ 的父亲节点的编号，节点的下标从 1 开始。特殊的，当 $j$ 为根时，输入中的第 $j$ 个值为 $0$。

我们保证对每棵族谱树来说， $1$ 号节点到 $n$ 号节点都是叶子，而 $n+1$ 到 $m$ 号节点都不是叶子。

同时，族谱树上的每个非叶节点至少有两个孩子。

输出格式

输出的第一行是一个正整数 $l$，表示答案族谱树中的点的数目。

接下来一行 $l$ 个整数，描述每个节点父亲的编号。

请注意：你所输出的树中的每个非叶节点也应至少有两个孩子，且只有 $1$ 号节点至 $n$ 号节点是叶子。

样例一

input

3 4
81 2 65 60
5
5 4 4 5 0
4
4 4 4 0
5
4 5 4 5 0
4
4 4 4 0

output

5
4 5 5 0 4

explanation

第一棵树的老家族有 $\{1\},\{2\},\{3\},\{2,3\},\{1,2,3\}$

第二棵树的老家族有 $\{1\},\{2\},\{3\},\{1,2,3\}$

第三棵树的老家族有 $\{1\},\{2\},\{3\},\{1,3\},\{1,2,3\}$

第四棵树的老家族有 $\{1\},\{2\},\{3\},\{1,2,3\}$

答案树的老家族有 $\{1\},\{2\},\{3\},\{2,3\},\{1,2,3\}$，这显然是字典序最大的方案。

样例二

input

10 4
5966 9271 8809 7834
18
13 11 14 12 12 13 17 17 11 16 14 16 15 15 18 17 18 0
14
13 14 11 11 14 11 11 12 13 12 12 13 14 0
16
15 12 15 13 16 11 13 12 11 14 12 15 14 15 16 0
18
11 12 12 18 16 14 15 13 11 11 13 16 14 15 17 17 18 0

output

16
14 16 12 15 11 12 15 13 14 13 0 13 14 16 12 11

样例三

见样例数据下载。

限制与约定

对于 $100\mathrm{\%}$ 的数据，$1\le w_i\le {10}^{16},1\le k\le 20,n\times k\le {10}^5$

Subtask 1 (10 分): $n\le 5$；

Subtask 2 (15 分): $n\le 100$；

Subtask 3 (30 分): $n\le 1000$；

Subtask 4 (20 分): 数据随机生成；

Subtask 5 (25 分): 无特殊限制。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{1GB}}$

下载

样例数据下载