D. Sweepstake
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kotlin Heroes competition is nearing completion. This time $$$n$$$ programmers took part in the competition. Now organizers are thinking how to entertain spectators as well. One of the possibilities is holding sweepstakes. So for now they decided to conduct a survey among spectators.

In total, organizers asked $$$m$$$ viewers two questions:

  1. Who will take the first place?
  2. Who will take the last place?

After receiving answers, organizers ranked all spectators based on the number of programmers they guessed right. Suppose, there are $$$c_2$$$ viewers who guessed right both first and last place, $$$c_1$$$ viewers who guessed either first or last place right and $$$c_0$$$ viewers who didn't guess at all. All $$$c_2$$$ viewers will get rank $$$1$$$, all viewers with one right answer will get rank $$$c_2 + 1$$$ and all remaining viewers — rank $$$c_2 + c_1 + 1$$$.

You were one of the interviewed spectators. Also, as one of the organizers, you have access to survey results, but not to competition results. Calculate, what is the worst rank you can possibly get according to organizers' ranking system?

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).

Examples
Input
2 3
1 2
2 1
2 1
Output
3
Input
3 6
3 1
3 2
2 1
3 2
3 2
3 1
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$$$).