UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3803. Idea Frame

Statistics 下载数据

Description

一个N个点M条边的无向图。有二种操作,第一种是将一个节点拆成
多个节点,每个新节点连接原有节点的某些边,且新节点边中的边没有
交,同时连的边的并集是原节点连的所有边。第二种操作是合并节点A,B
条件是A,B的度都是1.问有最少多少次操作可以将图变成一个环。
0<=N<=1000,1<=M<=5*10^4

Input

Output

Sample Input

6 8
1 2
1 3
3 4
1 4
4 6
5 6
4 5
1 5

Sample Output

4

Hint

Source