题目描述

系统发育树（phylogenetic tree）是一种根据不同物种或个体之间的相似性、物理特征和遗传特征等差异，表示其推测演化关系的图。它可以表示为一棵有根树。

智妍经过长期研究，提出了 $M$ 条关于 $N$ 个物种之间关系的假设。物种编号为 $1,2,\ldots,N$，智妍希望构造一棵系统发育树，使编号为 $i$ 的物种对应树中的顶点 $i$。

在一棵有根树中，若顶点 $x=y$，或者 $x$ 是 $y$ 的父节点的祖先，则称 $x$ 是 $y$ 的祖先。若 $x$ 是 $y$ 的祖先，则称 $y$ 是 $x$ 的后代。

两个顶点的最低公共祖先，是同时为这两个顶点祖先的顶点中深度最大的一个。

每条假设由四个整数 $(a,b,c,d)$ 表示。令

$$x=\operatorname{LCA}(a,b),\qquad y=\operatorname{LCA}(c,d).$$

这条假设要求 $x$ 是 $y$ 的严格后代，即 $x$ 是 $y$ 的后代且 $x\ne y$。

给定全部 $M$ 条假设，请构造一棵满足所有假设的系统发育树，其中物种 $i$ 对应顶点 $i$。

可以证明：若存在满足条件的树，则一定存在一棵所有顶点编号均不超过 $2N$ 的满足条件的树。

输入格式

第一行包含两个整数 $N,M$，分别表示物种数量和假设数量。

$$4\le N\le 2000,\qquad 1\le M\le 2000.$$

接下来 $M$ 行，每行包含四个整数 $a,b,c,d$，表示一条假设。

$$1\le a,b,c,d\le N,$$

并保证 $a\ne b$、$c\ne d$。

输出格式

若不存在满足所有假设的系统发育树，输出一行 -1。

否则：

• 第一行输出树的顶点数 $N'$，其中 $N\le N'\le 2N$；
• 第二行输出 $N'$ 个整数 $P_1,P_2,\ldots,P_{N'}$。

若顶点 $i$ 是根节点，则 $P_i=0$；否则 $P_i$ 是顶点 $i$ 的父节点编号。

若存在多种合法答案，输出任意一种即可。

样例 1

输入

6 2
1 2 3 5
2 5 1 4

输出

7
3 3 7 6 7 0 6

样例 2

输入

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

输出

-1