George and Interesting Graph

题意翻译

【题目描述】 George喜欢图，因此它想让图更有趣。他认为有趣的图满足以下条件： 没有重边； 存在结点v(称为中心)，使得对于图中的任意结点u，都有边(u,v)和(v,u)，注意自环(v,v)也应该存在； 除去中心外，每个点的入度和出度都恰好为2； 显然很少有图有趣，但George可以把图变得有趣：每次他可以增加一条边或者删除一条已经存在的边。 现在给出图 GG ，George想知道他最少做多少次操作可以使它变得有趣。 【输入格式】 第一行包含两个整数 n,mn,m ，表示结点数和边数。 接下来的m行每行包含两个整数 a,ba,b ，描述一条有向边 (a,b)(a,b) 。 输入保证不存在重边，结点从1开始计数。 【输出格式】 输出一个整数：问题的答案。 Translated by @Harry_bh

题目描述

George loves graphs. Most of all, he loves interesting graphs. We will assume that a directed graph is interesting, if it meets the following criteria: - The graph doesn't contain any multiple arcs; - There is vertex $ v $ (we'll call her the center), such that for any vertex of graph $ u $ , the graph contains arcs $ (u,v) $ and $ (v,u) $ . Please note that the graph also contains loop $ (v,v) $ . - The outdegree of all vertexes except for the center equals two and the indegree of all vertexes except for the center equals two. The outdegree of vertex $ u $ is the number of arcs that go out of $ u $ , the indegree of vertex $ u $ is the number of arcs that go in $ u $ . Please note that the graph can contain loops. However, not everything's that simple. George got a directed graph of $ n $ vertices and $ m $ arcs as a present. The graph didn't have any multiple arcs. As George loves interesting graphs, he wants to slightly alter the presented graph and transform it into an interesting one. In one alteration he can either remove an arbitrary existing arc from the graph or add an arbitrary arc to the graph. George wonders: what is the minimum number of changes that he needs to obtain an interesting graph from the graph he's got as a present? Help George and find the answer to the question.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ m $ ( $ 2<=n<=500,1<=m<=1000 $ ) — the number of vertices and arcs in the presented graph. Each of the next $ m $ lines contains two space-separated integers $ a_{i},b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ ) — the descriptions of the graph's arcs. Pair $ (a_{i},b_{i}) $ means that the graph contains an arc from vertex number $ a_{i} $ to vertex number $ b_{i} $ . It is guaranteed that the presented graph doesn't contain multiple arcs. Assume that the grah vertices are numbered 1 through $ n $ .

输出格式

Print a single integer — the answer to George's question.

输入输出样例

输入样例 #1

3 7
1 1
2 2
3 1
1 3
3 2
2 3
3 3

输出样例 #1

0

输入样例 #2

3 6
1 1
2 2
3 1
3 2
2 3
3 3

输出样例 #2

1

输入样例 #3

3 1
2 2

输出样例 #3

6

说明

For more information about directed graphs, please visit: http://en.wikipedia.org/wiki/Directed\_graph In the first sample the graph already is interesting, its center is vertex $ 3 $ .