Kotlin Heroes: Episode 8 |
---|

Finished |

The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 8:

- Kotlin 1.7.20
- Kotlin 1.9.21

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

*special problem

brute force

constructive algorithms

implementation

math

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Sweepstake

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKotlin 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:

- Who will take the first place?
- 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$$$).

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/18/2024 11:12:19 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|