系统发生树是一种展示基于各种物种或个体之间的相似性和差异性（包括物理和遗传特征）推断出的进化关系的图表。该图表表示为一棵有根树。

经过多年的研究，Ji-yeon 提出了 $m$ 个假设，旨在阐明 $n$ 个物种之间的相关性。每个物种都用 $1$ 到 $n$ 之间的一个唯一正整数标记。Ji-yeon 希望创建一棵包含 $n$ 个或更多顶点的系统发生树来验证她的研究，其中每个物种 $i$ 对应树中的顶点 $i$。

在有根树中，对于两个顶点 $x$ 和 $y$，如果 $x$ 和 $y$ 相同，或者 $x$ 是 $y$ 的父节点的祖先，则称顶点 $x$ 是顶点 $y$ 的祖先。如果顶点 $x$ 是顶点 $y$ 的祖先，则称顶点 $y$ 是顶点 $x$ 的后代。两个顶点 $x$ 和 $y$ 的最近公共祖先是同时为 $x$ 和 $y$ 的祖先且拥有最多祖先数量的那个顶点。

Ji-yeon 提出的假设形式为 $(a, b, c, d)$。每个假设声称：如果顶点 $a$ 和 $b$ 的最近公共祖先是顶点 $x$，且顶点 $c$ 和 $d$ 的最近公共祖先是顶点 $y$，那么顶点 $x$ 是顶点 $y$ 的后代，且顶点 $x$ 和 $y$ 不相同。

给定针对 $n$ 个物种的 $m$ 个假设，请创建一棵满足所有假设的系统发生树，或者确定不存在这样的树。树中的每个顶点 $i$ 应对应物种 $i$。此外，树中的顶点数 $n'$ 应在 $n$ 到 $2n$ 之间：可以证明，如果存在解，则一定存在一个顶点数不超过 $2n$ 的解。

输入格式

第一行包含两个整数 $n$ 和 $m$：Ji-yeon 研究的物种数量和假设的数量（$4 \le n \le 2000$；$1 \le m \le 2000$）。

接下来 $m$ 行，每行包含四个整数 $a, b, c, d$，表示一个假设（$1 \le a, b, c, d \le n$；$a \neq b$；$c \neq d$）。

输出格式

如果不存在满足所有假设的系统发生树，则在第一行输出 $-1$。否则，在第一行输出构成系统发生树的顶点数 $n'$（$n \le n' \le 2n$）。在第二行，输出 $n'$ 个整数 $p_1, p_2, \dots, p_{n'}$，以空格分隔。其中 $p_i$ 是顶点 $i$ 的父节点，如果顶点 $i$ 是根节点，则 $p_i$ 为 $0$。顶点的编号为 $1$ 到 $n'$，其中 $1$ 到 $n$ 号顶点对应各个物种。

如果存在多棵可能的系统发生树，输出其中任意一棵即可。

样例

样例输入 1

6 2
1 2 3 5
2 5 1 4

样例输出 1

7
3 3 7 6 7 0 6

样例输入 2

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

样例输出 2

-1