D. Лотерея
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Соревнование Kotlin Heroes близится к завершению. В этот раз в соревновании участвовало $$$n$$$ программистов. И теперь организаторы думают над тем, как развлечь еще и зрителей. Один из возможных вариантов — устроить лотерею. Но для начала нужно провести опрос среди зрителей.

В общем, организаторы опросили $$$m$$$ зрителей, каждому задали два вопроса:

  1. Кто займет первое место?
  2. Кто займет последнее место?

Получив все ответы, организаторы присвоили всем зрителям места на основании того, скольких программистов они угадали. Предположим, что $$$c_2$$$ зрителей правильно угадали и первое и последнее место, $$$c_1$$$ зрителей угадали только первое или только последнее место, и $$$c_0$$$ зрителей не угадали никого. Тогда все $$$c_2$$$ зрителей получат $$$1$$$-е место, все зрители с одним правильным местом получат место $$$c_2 + 1$$$, а все остальные — место $$$c_2 + c_1 + 1$$$.

Вы были одним из опрашиваемых зрителей. Кроме того, как один из организаторов, вы можете смотреть результаты опроса, но не результаты соревнования. Определите, какое наихудшее место вы можете занять согласно системе ранжирования организаторов?

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 1000$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — количество программистов, участвовавших в соревновании, и количество опрошенных зрителей.

В следующих $$$m$$$ строках заданы ответы зрителей. В $$$i$$$-й строке заданы два целых числа $$$f_i$$$ и $$$l_i$$$ ($$$1 \le f_i, l_i \le n$$$; $$$f_i \ne l_i$$$) — индексы программистов, кто займет первое и последнее места по мнению $$$i$$$-го зрителя.

Для простоты, ваш ответ всегда первый, то есть ваш ответ — это $$$f_1$$$ и $$$l_1$$$.

Выходные данные

Выведите одно целое число — худшее место, которое вы можете получить согласно системе ранжирования организаторов (чем больше место, тем хуже).

Примеры
Входные данные
2 3
1 2
2 1
2 1
Выходные данные
3
Входные данные
3 6
3 1
3 2
2 1
3 2
3 2
3 1
Выходные данные
4
Примечание

В первом примере, если второй программист займет первое место, а первый программист — последнее, то у вас будет $$$0$$$ правильных ответов в то время, как у других двух зрителей — $$$2$$$ правильных ответа. А потому ваше место (в худшем случае) будет равно $$$c_2 + c_1 + 1$$$ $$$=$$$ $$$2 + 0 + 1 = 3$$$.

Во втором примере, если, например, третий программист займет первое место, а второй программист — последнее место, то у вас будет $$$1$$$ правильный ответ. У зрителей $$$2$$$, $$$4$$$ и $$$5$$$ будет $$$2$$$ правильных ответа, у зрителя $$$6$$$ — $$$1$$$ правильный ответ, и у зрителя $$$3$$$ — $$$0$$$ правильных ответов. В результате ваше место будет равно $$$c_2 + 1$$$ $$$=$$$ $$$3 + 1 = 4$$$. (Заметим, что у зрителя $$$6$$$ также будет место $$$4$$$).