eolymp
bolt
Try our new interface for solving problems
Problems

New Island

New Island

Time limit 1 second
Memory limit 64 MiB

A new island has been discovered. A team of architects has worked hard and proposed a road plan to connect important parts of this new island. Due to lack of fund, we are to modify the design to come up with an affordable one.

In the proposed plan, each road has a unique id between 1 and E (the number of roads) and a cost that is unbelievably equal to 2^id. So, the costs are distinct powers of two. We want to eliminate some of the roads from the plan to get the minimum overall cost while all places are still connected. But, we should not eliminate as many roads as we want. The constraint is that in the new road plan the distance between any two places cannot become more than twice as their distance in the original plan. The distance between two places is the minimum number of roads connecting them. The original road plan is given to you in form of a graph and you are asked to find the most economic road elimination according to the constraint.

Input data

There are multiple test cases in the input. Each test case is started with a line containing two integers N (1N200) and E, the number of vertices (places) and edges (roads) respectively. The specification of the roads comes on the next E lines. The i^th line contains two numbers v_i and u_i which means that the road with idi is between places v_i and u_i. The input is terminated by a line containing two zero numbers.

Output data

For each test case, write the number of eliminated roads followed by the increasing list of their ids on a single line.

Examples

Input example #1
4 5
1 2
3 1
4 1
4 2
3 4
3 3
1 2
2 3
3 1
0 0
Output example #1
2 4 5
1 3
Source 32nd ACM International Collegiate, 9th Asian Regional Contest in Iran, December 6-7 2007 (Azar 15-16, 1386)