P17035 [NWERC 2020] 联合挖掘 / Joint Excavation

译自 [Northwestern Europe Regional Contest (NWERC) 2020](http://2020.nwerc.eu)。

鼹鼠一家最近决定挖一个新的隧道网络。布局已经确定好：它由若干洞室和连接它们的双向隧道组成，形成一个连通图。鼹鼠妈妈想借这个机会教她的两个鼹鼠孩子如何挖掘隧道网络。 作为一个快速的初步示范，鼹鼠妈妈打算先挖出计划隧道网络中的若干洞室和隧道，形式是一条不自交的路径。之后，她会把剩余洞室分给两个鼹鼠孩子，并确保每个孩子需要挖出的洞室数量相同，否则其中一个孩子会伤心。隧道要容易挖得多，因此不用考虑。孩子们可以按照任意顺序处理分配给自己的洞室。 由于两个鼹鼠孩子没有太多挖掘隧道网络的经验，鼹鼠妈妈意识到她的计划存在一个问题：如果某条隧道连接的两个洞室被分配给不同的孩子，那么在挖掘这条隧道时，如果另一个孩子恰好同时在连接的洞室中挖掘，就有发生事故的风险。 请帮助鼹鼠妈妈决定她初步示范时应使用哪条路径，以及如何把剩余洞室平均分给两个孩子，使得不存在一条隧道连接分别分配给两个不同孩子的洞室。初始路径必须包含至少一个洞室，并且不能重复经过同一个洞室。

输入包括： - 第一行包含两个整数 $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$ 个洞室，分别表示对应鼹鼠孩子需要挖出的洞室，顺序任意。 输入保证至少存在一个合法解。如果存在多个合法解，你可以输出任意一个。

【数据规模与约定】 - $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$。 - 任意两间洞室之间至多有一条隧道。 - 图连通。 - 保证至少存在一个合法解。