中心图
题号:NC236759
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给出一个 n 个节点, m 条边的有向图,你可以进行若干次操作,每次操作可以删除图中的一条边或者添加一条有向边,使得原图变为中心图。
定义一个图是中心图,当且仅当它满足如下条件:
1. 图中没有重边。
2. 存在一个点u,满足对于任意的  ,图中都存在边 (u,v) 和 (v,u) ,我们称 u 是中心点。注意:这意味着 u 需要有自环。
3. 除了中心点之外,其它所有点的入度和出度均为2。
此外,你需要保证操作次数尽可能少。

输入描述:

第一行输入两个整数  ,分别表示原图的点数和边数。
接下来m行,每行输入两个整数  ,表示从 u_i 到 v_i 有一条有向边相连。保证输入不含重边。

输出描述:

输出一行一个整数,表示让原图变为中心图需要的最小操作次数。
示例1

输入

复制
3 7
1 1
2 2
3 1
1 3
3 2
2 3
3 3

输出

复制
0

说明

给出的图已经是一个中心图,中心点是3。
示例2

输入

复制
3 1
2 2

输出

复制
6
示例3

输入

复制
3 6
1 1
2 2
3 1
3 2
2 3
3 3

输出

复制
1