Mr. Malnar 正在为他的 $2N$ 个合作伙伴举办一场宴会，这些合作伙伴被编号为 $1, 2, \dots, 2N$。合作伙伴们是成对来到宴会的。通过观察他们的行为，Mr. Malnar 注意到了一些支配该群体中信息传播的奇怪规则。

• 第一，当且仅当 A 和 B 是朋友时，A 愿意与 B 分享信息。成对来到宴会的两个合作伙伴是朋友。
• 第二，每个人最多愿意将信息分享给一个其他人。同时，该人此前必须不知道这个信息。
• 第三，每个人在尝试分享信息时，会优先分享给与他一同来到宴会的伙伴。 换句话说，如果 A 与 B 一同来到宴会，且 A 知道了某条信息而 B 还不知道，那么 A 会将该信息分享给 B。根据前述规则，A 将不会再把该信息分享给其他任何人，而 B 则会尝试将其分享给他的另一个朋友，以此类推。
• 第四，该群体可以被划分为两个子集，使得如果两个人是朋友，他们不在同一个子集中。

Mr. Malnar 将把他的故事告诉其中一位合作伙伴，他想知道最多能有多少个合作伙伴听到他的故事。如果这个最大数量为 $K$，他还想知道一个合作伙伴序列 $a_1, a_2, \dots, a_K$，使得如果他把故事告诉 $a_1$，那么对于每个 $i = 1, 2, \dots, K - 1$，合作伙伴 $a_i$ 都可以将故事告诉 $a_{i+1}$。

在发现上述规则的过程中，Mr. Malnar 确定了所有的朋友关系，但忘记了哪些合作伙伴是成对来到宴会的。幸运的是，这些信息是可以恢复的。换句话说，存在唯一的将合作伙伴划分为 $N$ 个配对的方法，使得同一配对中的合作伙伴是朋友。

你能帮助 Mr. 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 2 \cdot N$），表示编号为 $u_i$ 和 $v_i$ 的合作伙伴是朋友。

输出格式

第一行输出一个整数 $K$ — 能够听到 Mr. Malnar 故事的最大合作伙伴数量。

第二行输出一个包含 $K$ 个整数的序列，表示满足约束条件的合作伙伴序列。

子任务

样例

输入样例 1

2 3
1 2
1 4
3 4

输出样例 1

4
2 1 4 3

输入样例 2

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

输出样例 2

4
6 1 2 3

输入样例 3

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

输出样例 3

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 和 4，2 和 5，3 和 6，7 和 8。