题目描述

Berland Railways（BR）由 $n$ 个车站和若干条双向道路组成。任意两站之间至多有一条道路，没有自环。

铁路网络具有如下特殊结构：它由若干个“区域”组成，每个区域本身是一条简单环。每个区域恰好与两个不同的其他区域相邻，并分别与这两个区域共享一个车站。因此每个区域恰好有两个与相邻区域共享的车站，而所有区域在更高层次上也围成一个环。

于是每个车站只有两种可能：

• 只属于一个区域，度数为 $2$；
• 同时属于两个相邻区域，度数为 $4$。

现在有两家公司希望购买尽可能多的车站。反垄断委员会要求：任意一条道路的两个端点不能属于同一家公司。允许某些车站不被任何公司购买。

请给出一种购买方案，使两家公司购买的车站总数最大。

输入只给出车站和道路，不会直接告诉你各个区域如何划分。

输入格式

第一行两个整数 $n,m$，满足 $6\le n\le10^5$，$9\le m\le10^5$。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示车站 $a_i$ 与 $b_i$ 之间有一条双向道路。

保证输入网络满足题目描述中的特殊结构；区域数量至少为 $3$，每个区域至少包含 $3$ 个车站。

输出格式

第一行先输出整数 $n_1$，表示第一家公司购买的车站数量，随后输出这 $n_1$ 个车站的编号。

第二行先输出整数 $n_2$，表示第二家公司购买的车站数量，随后输出这 $n_2$ 个车站的编号。

要求任意道路的两个端点不能同时属于同一家公司，并且 $n_1+n_2$ 必须达到最大值。

如果有多种最优方案，输出任意一种。

样例 1

样例输入

14 18
1 2
1 4
1 7
1 8
2 4
3 4
3 14
4 5
5 6
6 14
7 11
7 10
7 9
8 9
10 12
11 14
12 13
13 14

样例输出

6 2 5 7 8 12 14
7 1 3 6 9 10 11 13

样例 2

样例输入

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

样例输出

2 2 5
2 1 3

说明

样例输出只是可行的最优方案之一；由于本题允许多解，其他满足条件且购买总数相同的方案同样正确。