Sweepstake

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 1000$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — the number of programmers participating in the competition and the number of surveyed spectators.

Next $$$m$$$ lines contain answers of spectators. The $$$i$$$-th line contains two integers $$$f_i$$$ and $$$l_i$$$ ($$$1 \le f_i, l_i \le n$$$; $$$f_i \ne l_i$$$) — the indices of programmers who will take the first and last places in opinion of the $$$i$$$-th viewer.

For simplicity, you are the first among spectators, so your answers are $$$f_1$$$ and $$$l_1$$$.

Output:

Print the single integer — the worst rank among spectators you can possibly get according to organizers' ranking system (bigger rank — worse, of course).

Sample Input:

2 3
1 2
2 1
2 1

Sample Output:

3

Sample Input:

3 6
3 1
3 2
2 1
3 2
3 2
3 1

Sample Output:

4

Note:

In the first example, if the second programmer takes first place, while the first programmer takes last place, you'll have $$$0$$$ right answers while the other two spectators — $$$2$$$ right answers. That's why your rank (in the worst case) will be $$$c_2 + c_1 + 1$$$ $$$=$$$ $$$2 + 0 + 1 = 3$$$.

In the second example, for example, if the third programmer takes the first place and the second programmer takes the last place, then you'll have $$$1$$$ right answer. The spectators $$$2$$$, $$$4$$$ and $$$5$$$ will have $$$2$$$ right answers, spectator $$$6$$$ — $$$1$$$ right answer and spectator $$$3$$$ — $$$0$$$ right answers. As a result, your rank will be equal to $$$c_2 + 1$$$ $$$=$$$ $$$3 + 1 = 4$$$. (Note that spectator $$$6$$$ will have the same rank $$$4$$$).