레이팅 미적용The mole family recently decided to dig a new tunnel network. The layout, which has already been decided, consists of chambers and bidirectional tunnels connecting them, forming a connected graph. Mother mole wants to use the opportunity to teach her two mole kids how to dig a tunnel network.
As an initial quick demonstration, mother mole is going to start by digging out a few of the chambers and tunnels, in the form of a non-self-intersecting path in the planned tunnel network. She will then divide the remaining chambers between the two mole kids, making sure that each mole kid has to dig out the same number of chambers, or else one of the mole kids will become sad. (The tunnels are much easier to dig out, and thus of no concern.) The kids may work on their assigned chambers in any order they like.
Since the mole kids do not have much experience with digging tunnel networks, mother mole realises one issue with her plan: if there is a tunnel between a pair of chambers that are assigned to different mole kids, there is a risk of an accident during the excavation of that tunnel if the other mole kid happens to be digging in the connecting chamber at the same time.
Help mother mole decide which path to use for her initial demonstration, and how to divide the remaining chambers evenly, so that no tunnel connects a pair of chambers assigned to different mole kids. The initial path must consist of at least one chamber and must not visit a chamber more than once.
The input consists of:
- One line with two integers \(c\) and \(t\) (\(1 \leq c \leq 2 \cdot 10^5\), \(0 \leq t \leq 2 \cdot 10^5\)), the number of chambers and tunnels in the planned tunnel network.
- \(t\) lines, each containing two integers \(a\) and \(b\) (\(1 \leq a,b \leq c\), \(a \neq b\)), describing a bidirectional tunnel between chambers \(a\) and \(b\).
The chambers are numbered from \(1\) to \(c\). There is at most one tunnel between any pair of chambers, and there exists a path in the network between any pair of chambers.
First output two integers \(p\) and \(s\), the number of chambers on the path in mother mole's initial demonstration and the number of chambers each mole kid has to dig out. Then output a line containing the \(p\) chambers in mother mole's initial path, in the order that she digs them out. Then output two more lines, each containing the \(s\) chambers that the respective mole kid has to dig out, in any order.
The input is chosen such that there exists at least one valid solution. If there are multiple valid solutions, you may output any one of them.
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