A bank's 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 is going to just set 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 the matter to her own hands and rushes to put a blockade on the earliest road that the robbers have to cross in order 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 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 2

Input:

3 2
2 3
1 2

Output:

2