题号:NC236759
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
给出一个

个节点,

条边的有向图,你可以进行若干次操作,每次操作可以删除图中的一条边或者添加一条有向边,使得原图变为中心图。
定义一个图是中心图,当且仅当它满足如下条件:
1. 图中没有重边。
2. 存在一个点

,满足对于任意的

,图中都存在边
)
和
)
,我们称

是中心点。注意:这意味着

需要有自环。
3. 除了中心点之外,其它所有点的入度和出度均为2。
此外,你需要保证操作次数尽可能少。
输入描述:
第一行输入两个整数
)
,分别表示原图的点数和边数。
接下来

行,每行输入两个整数
)
,表示从

到

有一条有向边相连。保证输入不含重边。
输出描述:
输出一行一个整数,表示让原图变为中心图需要的最小操作次数。
示例1
输入
复制
3 7
1 1
2 2
3 1
1 3
3 2
2 3
3 3
示例3
输入
复制
3 6
1 1
2 2
3 1
3 2
2 3
3 3