• 来源：48th Petrozavodsk Programming Camp, Winter 2025，Day 3: K-ontest 1，Problem A
• 原题名：Advanced Evolution Studies
• 时间限制：2 秒
• 空间限制：1024 MiB

题目描述

研究员 Ji-yeon 正在整理一批星际生物的演化档案。她希望用一棵有根树表示这些生物之间的演化关系：树上的叶子或内部节点都可以代表某个演化阶段，而编号为 $1$ 到 $n$ 的 $n$ 个节点必须分别对应她已经研究过的 $n$ 个物种。

对于有根树中的两个节点 $x,y$，若 $x=y$，或 $x$ 是 $y$ 的父节点的祖先，则称 $x$ 是 $y$ 的祖先，$y$ 是 $x$ 的后代。两个节点 $x,y$ 的最近公共祖先记为 $\operatorname{lca}(x,y)$。

Ji-yeon 提出了 $m$ 条演化假设。每条假设形如四元组 $(a,b,c,d)$，含义如下：

设

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

那么必须满足：

• $x$ 是 $y$ 的后代；
• $x$ 与 $y$ 不是同一个节点。

也就是说，这条假设要求 $\operatorname{lca}(a,b)$ 严格位于 $\operatorname{lca}(c,d)$ 的子树中。

请你帮助 Ji-yeon 构造一棵满足所有假设的有根树，或者判断这样的树不存在。

构造出的树可以含有额外节点。若最终树的节点数为 $N'$，则必须满足

$$n\le N'\le 2n.$$

题目保证：如果存在合法答案，则一定存在节点数不超过 $2n$ 的合法答案。

输入格式

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

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

输出格式

如果不存在满足所有假设的有根树，输出一行：

-1

否则，第一行输出一个整数 $N'$，表示构造出的树的节点数。

第二行输出 $N'$ 个整数

$$p_1,p_2,\ldots,p_{N'},$$

其中 $p_i$ 表示节点 $i$ 的父节点编号；若节点 $i$ 是根，则 $p_i=0$。

节点 $1$ 到 $n$ 必须分别对应原来的 $n$ 个物种。若有多种合法构造，输出任意一种即可。

数据范围

• $4\le n\le 2000$；
• $1\le m\le 2000$；
• $1\le a,b,c,d\le n$；
• $a\ne b$；
• $c\ne d$。

样例 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