401687: GYM100513 L Useful Roads

Berland capital contains n junctions and m roads connecting pairs of junctions. All roads are one-way. As you probably know Berland has two misfortunes: fools and roads.

It is one month before mayoral election. So it is time for current government to make the city better. To show that they care both about the infrastructure and about the budget, the government decided to repair only useful roads.

Current mayor thinks that a road from a junction u to a junction v is useful if there exists a simple path from City Hall to some junction containing the road (u, v). A path is called simple if it does not have any repeated junctions, i.e. contains each junction at most once. The City Hall is located at the junction 1.

Help Ministry of Road Transport and Highways to find all useful roads in the city.

The input contains several test cases. Each test case starts with a line containing two integers n, m (2 ≤ n ≤ 2·10⁵;1 ≤ m ≤ 2·10⁵) — the number of junctions and the number of roads in the city. The following m lines contain road descriptions, one description per line. A description consists of a pair of space-separated integers u_i, v_i (1 ≤ u_i, v_i ≤ n;u_i ≠ v_i) meaning that the i-th road leads from the junction u_i to the junction v_i. The junctions are numbered from 1 to n. The City Hall is located at the junction 1.

It is guaranteed that there is at most one road between a pair of junctions in each direction.

There is a blank line after each test case. The sum of n over all test cases in the input doesn't exceed 2·10⁵. The same is true for m: the sum of m over all test cases in the input doesn't exceed 2·10⁵.

Print two lines for each test case. On the first line print the number of useful roads. The second line should contain the indices of useful roads in ascending order. The roads are indexed from 1 to m in order of appearance in the input. Leave the second line empty if there are no useful roads in the city.

5 7
1 2
5 2
2 3
3 4
4 5
2 4
4 2 


2 1
1 2 

5
1 3 4 5 6
1
1