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

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

  • В графе отсутствуют кратные дуги.
  • Существует такая вершина 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.