← 返回题目列表

Codeforces · 387/D

D. 乔治和有趣的图表

中文机器翻译题面 查看原题

乔治喜欢图表。最重要的是,他喜欢有趣的图表。如果有向图满足以下条件,我们将假设它是有趣的:

- 图形不包含任何多条弧;
- 存在顶点 v(我们将其称为中心),因此对于图 u 的任何顶点,该图都包含弧 (u, v) 和 (v, u)。请注意,该图还包含循环 (v, v)。
- 除中心之外的所有顶点的出度都等于 2,并且除中心之外的所有顶点的入度都等于 2。顶点u的出度是从u出去的弧的数量,顶点u的入度是从u进入的弧的数量。请注意,图表可以包含循环。

然而,并非一切都那么简单。乔治得到了一个有 n 个顶点和 m 条弧的有向图作为礼物。该图没有任何多条弧。由于乔治喜欢有趣的图表,他想稍微改变一下呈现的图表,将其变成一个有趣的图表。在一种改变中,他可以从图中删除任意现有的弧,或者向图中添加任意弧。

乔治想知道:要从他收到的礼物图表中获得有趣的图表,他需要进行的最少更改次数是多少?帮助乔治找到问题的答案。

输入

第一行包含两个空格分隔的整数 n 和 m (2 ≤ n ≤ 500, 1 ≤ m ≤ 1000) — 所呈现图中的顶点和弧的数量。

接下来的 m 行中的每一行都包含两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n) — 图形弧的描述。 Pair(ai,bi)表示该图包含从顶点编号ai到顶点编号bi的弧。保证所呈现的图形不包含多个弧。

假设图顶点编号为 1 到 n。

输出

打印一个整数——乔治问题的答案。

示例

输入 #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

注意

有关有向图的更多信息,请访问:http://en.wikipedia.org/wiki/Directed_graph

在第一个示例中,该图已经很有趣,它的中心是顶点 3。