A bank has been robbed! Fortunately, the robbers have chosen their target exceptionally poorly: the bank resides on an island that has only one bridge out. The police are just going to set a blockade on the bridge and wait for the thieves to come to them.

However, as a young and aspiring police officer, Maija is having none of it. The robbers couldn't possibly be that stupid! She decides to take matters into her own hands and rushes to put a blockade on the earliest road that the robbers have to cross to exit the island.

There are n junctions numbered 1,2,\dots,n and m bidirectional roads connecting them, numbered 1,2,\dots,m. The i-th road connects junctions a_i and b_i. The bank resides at junction 1, and the bridge at junction n. There is guaranteed to be a path between every pair of junctions.

Input

The first line contains two integers n and m. The i-th of the next m lines contains two integers a_i and b_i.

Output

Print the index of the road that Maija should blockade, or 0 if the bridge is the only road guaranteed to be on the robbers' path.

Constraints

• 2 \leq n \leq 10^5
• 1 \leq m \leq 2 \times 10^5
• 1 \leq a_i, b_i \leq n
• (a_i, b_i) \neq (a_j, b_j) if i \neq j

Example 1

Input:

5 6
1 4
3 4
4 5
2 3
2 4
1 2

Output:

3

Example 2

Input:

4 4
1 2
1 3
2 4
3 4

Output:

0

Example 3

Input:

3 2
2 3
1 2

Output:

2