404694: GYM101611 E Empire History

Long time ago, there were two great Kingdoms Someland and Otherland. Each of them consisted of at least two cities and some roads connecting them. It was possible to get from any city of any kingdom to any other city of this kingdom using only these roads. However, no two cities of different kingdoms were connected by a road.

As an old legend says, when both kingdoms were conquered by the Emperor of New Roads, he decided to unite them by doing what he was very well known for — by building new roads. He picked some non-empty subset of cities of Someland u₁, u₂, ..., u_k and some non-empty subset of cities of Otherland v₁, v₂, ..., v_l. Then, he ordered to build a new road between each pair of cities u_x and v_y (1 ≤ x ≤ k, 1 ≤ y ≤ l), thus adding k·l new roads.

Hundreds of years have passed. Since then, no new cities and no new roads were built, and no cities or roads were destroyed. However, no one actually remembers which cities were part of Someland and which cities were part of Otherland. This year, the empire plans to celebrate millennium, and you were hired to restore the historical truth and determine the possible division of cities between Someland and Otherland.

The first line of the input contains two integers n and m (4 ≤ n ≤ 200 000, n - 1 ≤ m ≤ 200 000) — the number of cities and the number of roads in the current map of the empire.

Each of the next m lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) — the indices of cities connected by the i-th road. No road connects city with itself, and no two roads connect the same pair of cities.

The first line of the output should contain two integers n₁ and k (2 ≤ n₁ ≤ n - 2, 1 ≤ k ≤ n₁) — the number of cities in Someland and the number of cities of Someland selected by the Emperor of New Roads.

The second line should contain n₁ distinct integers — indices of the cities of the empire that one day were part of Someland. First k of them should denote the subset selected for building new roads.

The third line should contain two integers n₂ and l (n₂ = n - n₁, 1 ≤ l ≤ n₂) — the number of cities in Otherland and the number of cities of Otherland selected to build the new roads.

The fourth line should list cities of Otherland in the same format as the cities of Someland.

In your solution, both Someland and Otherland should be connected. As no one really cares how these two kingdoms looked like, if there are several possible solutions, print any of them. It is guaranteed that at least one possible solution exists.

6 12
1 2
1 3
2 3
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6

4 4
3 4 5 6
2 2
1 2

6 10
1 2
1 3
1 4
1 5
6 2
6 3
6 4
6 5
2 3
4 5

2 2
4 5
4 2
1 6 2 3