Sweepstake
Contest: Kotlin Heroes: Episode 8
Difficulty rating: 1800
Tags: *special, brute force, constructive algorithms, implementation, math

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 format:
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 format:
Print the single integer — the worst rank among spectators you can possibly get according to organizers' ranking system (bigger rank — worse, of course).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
2 3
1 2
2 1
2 1

Example output:
3

Example input:
3 6
3 1
3 2
2 1
3 2
3 2
3 1

Example output:
4

Editorial:
Let's iterate over all possible pairs (winner, looser), calculate our place and take a maximum among all of them.
Suppose, $$$\mathit{cntPairs}_{w, l}$$$ be the number of spectators who chose pair winner $$$w$$$ and looser $$$l$$$, $$$\mathit{cntFirst}_w$$$ be the number of spectators who chose $$$w$$$ as winner, and $$$\mathit{cntLast}_l$$$ be the number of spectators who chose $$$l$$$ as looser.
Then, for a fixed pair (winner $$$w$$$ and looser $$$l$$$) it's possible to calculate both $$$c_2$$$ and $$$c_1$$$ in the following way: $$$c_2 = \mathit{cntPairs}_{w, l}$$$ and $$$c_1 = \mathit{cntFirst}_w + \mathit{cntLast}_l - 2 \mathit{cntPairs}_{w, l}$$$ (because, both $$$\mathit{cntFirst}_w$$$ and $$$\mathit{cntLast}_l$$$ contain spectators who guessed $$$2$$$ results). After that, baced on the number of our right answers, we can calculate our rank: is it $$$1$$$, $$$c_2 + 1$$$ or $$$c_2 + c_1 + 1$$$.
But there is one simplification: it can be proved that we can always iterate only over pairs $$$(w, l)$$$ where we guessed $$$0$$$ right answers. In this case our rank will always be $$$c_2 + c_1 + 1$$$ $$$=$$$ $$$\mathit{cntFirst}_w + \mathit{cntLast}_l - \mathit{cntPairs}_{w, l} + 1$$$ (union of all spectators who answered right at least once).