黑暗爆炸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