Two spanning trees

Very hard

Execution time limit is 2 seconds

Runtime memory usage limit is 256 megabytes

Given an undirected graph, you need to divide its edges into two disjoint spanning trees. Your task is to find such a division.

Input

The first line contains two natural numbers, n and m, representing the number of vertices and edges in the graph, respectively. The following m lines describe the edges of the graph, with each edge specified by the numbers of its endpoints. It is guaranteed that the graph contains no loops, but there may be multiple edges between the same pair of vertices.

Vertices and edges in the graph are numbered starting from one. The number of vertices does not exceed 500, and the number of edges does not exceed 1000.

Output

Output the required division of the graph's edges. On the first line, list the numbers of the edges that will form the first spanning tree. On the second line, list the numbers of the edges that will form the second spanning tree. Each edge in the graph must be included in exactly one of these two lines.

Submissions 8