541. BR Privatization

Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Berland Railways (BR) is about to finish their existence as public property. Privatization is approaching.

Currently, BR consists of n stations, some pairs are connected by bidirectional roads. Between each pair of stations there is no more than one road and any road connects exactly two different stations.

Since each Berland railway network was developed independently, the topology of BR has an interesting form. BR consists of areas. Each area is a set of stations connected in a cycle in some order. Each area borders with exactly two different other areas and shares a single station with each of them. So exactly two stations in each area are shared by neighbouring areas. Thus, each station Since the BR form a connected network, one can say that the areas also form a single cycle of areas.

The figure below illustrates BR's possible structure.

In this case BR has 14 stations, 18 roads and consists of four areas numbered from 1 to 4:

Two major companies are planning to buy most of the BR stations. However the antitrust committee has its own requirements. No two stations connected by a road should belong to the same company. It frustrates the owners of the first and the second company, they may not even be able to purchase all the stations without violating this condition.

Both companies have decided to buy stations in such a way that the total number of stations purchased by both companies is maximal. If there are multiple ways for such distribution, they agree on any of them.

Help them to carry out their plans, write a program that finds the desired buying plan. Note that the information about BR is given to you as a list of stations and roads, but the information about areas is not explicitly defined.

The first line contains a pair of integers n, m (6 ≤ n ≤ 105; 9 ≤ m ≤ 105), where n is the number of stations, and m is the number of roads. All stations are arbitrarily numbered from 1 to n. Then m lines follow, each containing a pair of integers ai,bi (1 ≤ ai,bin; aibi) and indicating the road that connects the stations with numbers ai and bi. The roads are given in arbitrary order.

BR consists of at least three areas, each contains at least three stations.

In the first line print non-negative integer number n1 — the number of stations to be purchased by the first company. Then n1 numbers follow — the numbers of stations to be purchased by the first company.

In the second line print non-negative integer number n2 — the number of stations to be purchased by the second company. Then n2 numbers follow — the numbers of stations to be purchased by the second company.

If there are multiple solutions, print any of them.

sample input
sample output
14 18
1 2
1 4
1 7
1 8
2 4
3 4
3 14
4 5
5 6
6 14
7 11
7 10
7 9
8 9
10 12
11 14
12 13
13 14
6 2 5 7 8 12 14
7 1 3 6 9 10 11 13

sample input
sample output
6 9
1 2
1 6
2 6
2 4
2 3
3 4
4 6
4 5
5 6
2 2 5
2 1 3

The first example corresponds to the illustration from the problem statement.

Online Contester Team © 2002 - 2010. All rights reserved.