Company Trip

Company trip

Problem Statement

Your company has n employees. For a group of m employees (a_i, b_i), a_i is the boss of b_i.

When employee x is the actual boss of employee y, it means that at least one of the following holds.

• x is y's boss.
• There is an employee z who is the actual boss of y, and x is the boss of z.

There are no employees in your company who are their actual bosses.

Your company is planning an employee trip with all employees participating. At the request of all employees, the room allocation at the inn must be "good room allocation". A "good room allocation" means that both of the following are satisfied.

• Each employee is assigned to some room.
• When employee x and employee y are assigned to the same room, x is not the actual boss of y.

Since the secretary's employees are very talented, we allocated the rooms so that they were "good room allocation" and the number of required rooms was minimized. But unfortunately the budget is insufficient. It seems that the number of rooms required must be reduced. Therefore, you who work in the human resources department decided to reduce the number of rooms required to obtain a "good room allocation" by eliminating only one boss-subordinate relationship. Now, which relationship should be resolved?

Constraints

• 2 ≤ n ≤ 10 ^ 5
• 1 ≤ m ≤ 2 \ times 10 ^ 5
• 1 ≤ a_i <b_i ≤ n
• If i \ neq j, then (a_i, b_i) \ neq (a_j, b_j)

Input

Input follows the following format. All given numbers are integers.

n m a_1 b_1 ... a_m b_m

Output

Output i that satisfies the following in ascending order, line by line.

• When the relationship "a_i is the boss of b_i" is resolved, the number of rooms required to obtain "good room allocation" can be reduced.

If such i does not exist, output -1 on one line.

Example

Input

5 4 1 2 2 3 3 4 3 5

Output

1 2

inputFormat

Input

Input follows the following format. All given numbers are integers.

n m a_1 b_1 ... a_m b_m

outputFormat

Output

Output i that satisfies the following in ascending order, line by line.

• When the relationship "a_i is the boss of b_i" is resolved, the number of rooms required to obtain "good room allocation" can be reduced.

If such i does not exist, output -1 on one line.

Example

Input

5 4 1 2 2 3 3 4 3 5

Output

1 2

样例

5 4
1 2
2 3
3 4
3 5

1
2

</p>