Sumo

Time limit1sMemory limit128 MB

Summary

Find the earliest scheduled fight that forces two wrestlers on the same team to meet under the best two-team split.

Level: Medium5 of 10
Topics: Union-find, Graph
Solved: No attempts yet

Problem

A Japanese monastery known for strict fasting and ascetic life runs a sumo section, and its Head decided to organise training fights for his $N$ wrestlers. He fixed the exact order of $M$ fights and the two wrestlers who meet in each one.

Moments before the first fight, the Head realised he could make the training more interesting. He could split the wrestlers into two teams so that every fight puts one team against the other. The schedule is already set and cannot be touched for whatever zen reason, and under this schedule no such split exists. That leaves one option: split the wrestlers into two teams so that the first fight between two members of the same team comes as late as possible.

Given the schedule, find the ordinal number of the first fight in which two wrestlers of the same team have to meet, assuming the teams are chosen in the best possible way. In every input such a fight does occur.

Input

The first line contains the number of wrestlers $N$ ( $1 \le N \le 100\,000$ ). The wrestlers are numbered from $1$ to $N$ .

The second line contains the number of fights $M$ ( $1 \le M \le 300\,000$ ).

Each of the next $M$ lines describes one fight, in the order the fights take place. Each line contains two different integers from $[1, N]$ , the numbers of the two wrestlers who meet.

Output

Print the ordinal number of the first fight between two wrestlers of the same team. This number is between $1$ and $M$ .

Examples2

Example 1
Input
```
5
5
1 2
2 3
3 4
4 5
5 1
```
Expected output
```
5
```
Example 2
Input
```
6
8
1 2
3 4
5 6
1 3
1 6
4 5
2 4
2 6
```
Expected output
```
6
```