背景

译自 Northwestern Europe Regional Contest (NWERC) 2020。

题目描述

鼹鼠一家最近决定挖一个新的隧道网络。布局已经确定好：它由若干洞室和连接它们的双向隧道组成，形成一个连通图。鼹鼠妈妈想借这个机会教她的两个鼹鼠孩子如何挖掘隧道网络。

作为一个快速的初步示范，鼹鼠妈妈打算先挖出计划隧道网络中的若干洞室和隧道，形式是一条不自交的路径。之后，她会把剩余洞室分给两个鼹鼠孩子，并确保每个孩子需要挖出的洞室数量相同，否则其中一个孩子会伤心。隧道要容易挖得多，因此不用考虑。孩子们可以按照任意顺序处理分配给自己的洞室。

由于两个鼹鼠孩子没有太多挖掘隧道网络的经验，鼹鼠妈妈意识到她的计划存在一个问题：如果某条隧道连接的两个洞室被分配给不同的孩子，那么在挖掘这条隧道时，如果另一个孩子恰好同时在连接的洞室中挖掘，就有发生事故的风险。

请帮助鼹鼠妈妈决定她初步示范时应使用哪条路径，以及如何把剩余洞室平均分给两个孩子，使得不存在一条隧道连接分别分配给两个不同孩子的洞室。初始路径必须包含至少一个洞室，并且不能重复经过同一个洞室。

输入格式

输入包括：

• 第一行包含两个整数 $c$ 和 $t$（$1 \le c \le 2\cdot 10^5$，$0 \le t \le 2\cdot 10^5$），分别表示计划隧道网络中洞室和隧道的数量。
• 接下来 $t$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a,b \le c$，$a\ne b$），表示洞室 $a$ 和洞室 $b$ 之间有一条双向隧道。

洞室编号为 $1$ 到 $c$。任意一对洞室之间至多有一条隧道，并且网络中任意两间洞室之间都存在一条路径。

输出格式

首先输出两个整数 $p$ 和 $s$，分别表示鼹鼠妈妈初步示范路径上的洞室数量，以及每个鼹鼠孩子需要挖出的洞室数量。然后输出一行，包含鼹鼠妈妈初始路径中的 $p$ 个洞室，按她挖掘它们的顺序输出。之后再输出两行，每行包含 $s$ 个洞室，分别表示对应鼹鼠孩子需要挖出的洞室，顺序任意。

输入保证至少存在一个合法解。如果存在多个合法解，你可以输出任意一个。

3 2
3 1
2 1

3 0
3 1 2

4 3
1 3
2 3
3 4

2 1
3 4
2
1

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

3 2
5 2 7
6 1
3 4

提示

【数据规模与约定】

• $1 \le c \le 2\cdot 10^5$。
• $0 \le t \le 2\cdot 10^5$。
• 每条隧道满足 $1 \le a,b \le c$ 且 $a \ne b$。
• 任意两间洞室之间至多有一条隧道。
• 图连通。
• 保证至少存在一个合法解。