题目背景

本题满分 $110$。

题目描述

Malnar 先生正在为他的 $2N$ 位同事举办宴会，同事编号为 $1,2,\dots,2N$。同事们是两两成对来到宴会的。Malnar 先生观察到这群人传播信息时遵循一些奇怪规则：

第一，当且仅当两人是朋友，A 才愿意把信息告诉 B。保证一起到宴会的那一对同事互为朋友。

第二，每个人最多只愿意向一个人分享信息，并且对方必须尚未知道该信息。

第三，每个人尝试分享信息时，优先级最高的是与自己同来宴会的搭档。

换句话说：若 A 与 B 同来宴会，并且 A 知道而 B 不知道某信息，则 A 一定会把信息告诉 B。由于规则 2，A 不会再把该信息告诉其他人；而 B 之后会尝试把信息告诉另一位朋友，如此继续。

第四，这群人可以被划分为两个子集，使得任意一对朋友都不在同一子集。

Malnar 先生打算把故事讲给其中一位同事，并关心最多能有多少位同事听到故事。若最大人数为 $K$，他还希望你给出一个长度为 $K$ 的序列 $a_1,a_2,\ldots,a_K$，使得如果他把故事讲给 $a_1$，那么对所有 $i=1,2,\ldots,K-1$，同事 $a_i$ 都能把故事讲给 $a_{i+1}$（符合上述传播规则）。

在整理规则时，Malnar 先生记录下了所有“朋友关系”，但忘记了当初哪些同事是成对来到宴会的。幸运的是，这些信息可以被唯一恢复：也就是说，存在且仅存在一种把 $2N$ 位同事划分为 $N$ 对的方式，使得同一对里的两人是朋友。

请你帮助 Malnar 先生回答上述问题。

输入格式

第一行包含两个整数 $N, M$（$1 \le N \le 5\cdot 10^5$，$N \le M \le 10^6$），分别表示参加宴会的同事“对数”与朋友关系条数。

接下来 $M$ 行，每行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le 2N$），表示 $u_i$ 与 $v_i$ 是朋友。

输出格式

第一行包含一个整数 $K$，表示最多能听到故事的人数。

第二行包含 $K$ 个整数，给出满足条件的序列。若有多种可能的答案，输出任意一种即可。

2 3
1 2
1 4
3 4

4
2 1 4 3

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

4
6 1 2 3

4 8
1 2
2 3
3 4
4 1
2 5
3 6
4 7
7 8

6
6 3 4 1 2 5

提示

【样例解释】

样例 #1 解释：参加宴会的同事配对为：$(1,2)$、$(3,4)$。

样例 #2 解释：参加宴会的同事配对为：$(1,6)$、$(2,3)$、$(4,5)$。可以证明不存在更长的可行序列。

例如序列 $(3,2,1,4,5)$，虽然相邻两人都是朋友，但 $1$ 从 $2$ 听到故事后无法把故事告诉 $4$，因为 $1$ 的宴会搭档 $6$ 仍不知道故事（规则 3 的优先级阻止了该传播）。

【子任务】

子任务	分值	限制
$1$	$24$	$N \le 10$
$2$	$16$	每位同事最多与 $2$ 位同事是朋友
$3$	$30$	$N \le 2000$，$M \le 5000$
$4$	$40$	无额外限制