Георгий любит графы. Особенно он любит интересные графы. Будем называть ориентированный граф интересным, если выполнены все следующие условия:
- В графе отсутствуют кратные дуги.
- Существует такая вершина v (будем называть ее центром), что для любой вершины графа u в графе содержатся дуги (u, v) и (v, u). При этом стоит отметить, что петля (v, v) должна содержаться в графе.
- Степень исхода каждой вершины кроме центра равна двум, степень захода каждой вершины кроме центра равна двум. Степень исхода вершины u — количество исходящих из u дуг, степень захода вершины u — количество входящих в u дуг. Стоит отметить, что граф может содержать петли.
Однако, не все так просто. Георгию подарили ориентированный граф, состоящий из n вершин и m дуг. В подаренном графе отсутствовали кратные дуги. Поскольку Георгий любит интересные графы, он хочет немного изменить подаренный граф так, чтобы получить интересный. За одно изменение разрешается удалить произвольную существующую дугу в графе, либо добавить произвольную дугу в граф.
Георгий интересуется: какое минимальное количество изменений потребуется, чтобы из подаренного графа получить интересный граф? Помогите Георгию и узнайте ответ на поставленный вопрос.
Выходные данные
Выведите единственное целое число — ответ на поставленный Георгием вопрос.
Примечание
Если вы не знакомы с ориентированными графами, то можете изучить их здесь: http://ru.wikipedia.org/wiki/Ориентированный_граф
В первом примере граф уже является интересным, и его центром является вершина 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 7
1 1
2 2
3 1
1 3
3 2
2 3
3 3
|
0
|
|
2
|
3 6
1 1
2 2
3 1
3 2
2 3
3 3
|
1
|
|
3
|
3 1
2 2
|
6
|