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

Георгий любит графы. Особенно он любит интересные графы. Будем называть ориентированный граф интересным, если выполнены все следующие условия:

  • В графе отсутствуют кратные дуги.
  • Существует такая вершина v (будем называть ее центром), что для любой вершины графа u в графе содержатся дуги (u, v) и (v, u). При этом стоит отметить, что петля (v, v) должна содержаться в графе.
  • Степень исхода каждой вершины кроме центра равна двум, степень захода каждой вершины кроме центра равна двум. Степень исхода вершины u — количество исходящих из u дуг, степень захода вершины u — количество входящих в u дуг. Стоит отметить, что граф может содержать петли.

Однако, не все так просто. Георгию подарили ориентированный граф, состоящий из n вершин и m дуг. В подаренном графе отсутствовали кратные дуги. Поскольку Георгий любит интересные графы, он хочет немного изменить подаренный граф так, чтобы получить интересный. За одно изменение разрешается удалить произвольную существующую дугу в графе, либо добавить произвольную дугу в граф.

Георгий интересуется: какое минимальное количество изменений потребуется, чтобы из подаренного графа получить интересный граф? Помогите Георгию и узнайте ответ на поставленный вопрос.

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

В первой строке содержатся два целых числа через пробел n и m (2 ≤ n ≤ 500, 1 ≤ m ≤ 1000) — количество вершин и дуг в подаренном графе.

В следующих m строках заданы по два целых числа через пробел ai, bi (1 ≤ ai, bi ≤ n) — описания дуг графа. Пара (ai, bi) означает, что в графе имеется дуга, исходящая из вершины c номером ai и заходящая в вершину с номером bi. Гарантируется, что подаренный граф не содержит кратных дуг.

Считайте, что вершины графа пронумерованы от 1 до n.

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

Выведите единственное целое число — ответ на поставленный Георгием вопрос.

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

Если вы не знакомы с ориентированными графами, то можете изучить их здесь: http://ru.wikipedia.org/wiki/Ориентированный_граф

В первом примере граф уже является интересным, и его центром является вершина 3.