다중 그래프의 경로

면접 대비

시간 제한2초메모리 제한512 MB

요약

무향 다중 그래프에서 간선을 최소 몇 개 지워야 남은 그래프가 연결되지 않게 되는지 구한다.

난이도: 보통10점 중 6점
유형: 그래프, 최소 신장 트리, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

루프가 없는 무향 다중 그래프 $G$ 가 주어진다. 두 정점 사이에 간선이 여러 개 놓일 수 있고, 한 정점을 자기 자신과 잇는 간선은 없다.

$G$ 에서 간선을 몇 개 지워 연결 그래프가 아니게 만들려고 한다. 지워야 하는 간선 개수의 최솟값을 구하라. 정점 두 개를 골랐을 때 그 사이에 경로가 없는 쌍이 하나라도 있으면 그래프는 연결되어 있지 않다. 따라서 $G$ 가 이미 연결 그래프가 아니면 간선을 하나도 지우지 않아도 된다.

입력

첫째 줄에 $G$ 의 정점 개수 $n$ 이 주어진다. 정점에는 $1$ 번부터 $n$ 번까지 번호가 붙어 있다. 둘째 줄에 간선 개수 $m$ 이 주어진다. 이어지는 $m$ 개 줄에 각 간선의 양 끝점 $u$ 와 $v$ 가 주어진다.

출력

첫째 줄에 $G$ 를 연결 그래프가 아니게 만들기 위해 지워야 하는 간선 개수의 최솟값을 출력한다.

제한

$2 \le n \le 100$
$0 \le m \le 3000$
$1 \le u, v \le n$ 이고 $u \ne v$

예제3

예제 1
입력
```
2
3
1 2
1 2
1 2
```
예상 출력
```
3
```
예제 2
입력
```
3
2
1 2
2 3
```
예상 출력
```
1
```
예제 3
입력
```
3
1
1 2
```
예상 출력
```
0
```