#215714. [ICPC 2025 Jakarta R] Two Sets

You are given an undirected graph with vertices and edges, with vertices numbered from to .

You have to select two integers and such that:

• There exists a non-empty set of vertices such that for every vertex , there are other vertices in that share an edge with .
• There exists a set of vertices of size such that for every vertex , there are no vertices in that share an edge with .

You have to find , , along with any and that satisfy the requirements above. It can be proven that such and always exist.

The first line contains two integers and (; )).

Each of the next lines contains two integers and () representing the two vertex numbers that are connected by an edge.

All the given edges are different.

The first line contains two integers and .

The second line contains an integer followed by integers representing the vertex numbers in .

The third line contains an integer followed by integers representing the vertex numbers in .

样例输入 1

4 2
1 2
3 4

样例输出 1

1 2
2 1 2
2 3 1

You selected , , , and .