Problem
오세아니아 섬에 흩어져 있는 한 주는 도로망(또는 다리)을 만들기로 결정했습니다. 각 다리는 양방향으로 탐색할 수 있습니다. 교량 건설을 위한 순서 계획이 개발되었으며 모든 교량 건설 후 각 섬에서 각 섬으로 다리를 건너가는 것이 가능할 것으로 알려져 있습니다(아마도 일부 중간 섬을 통해
그러나 모든 다리가 건설되기 전에 이 순간이 올 수 있습니다. 건설 후 (계획에 따라 결정된 순서대로) 섬에서 다른 섬으로 이동할 수 있는 최소 교량 수를 결정해야 합니다.
입력
첫 번째 줄에는 섬의 수 N(1≤N≤10000)과 계획 M의 다리 수(1≤M≤50000)라는 두 개의 숫자가 있습니다. 그런 다음 각각 두 개의 숫자 x와 y(1≤x,y≤N)를 포함하는 M개의 라인이 있습니다. 이 라인은 계획에서 다음 다리로 연결된 도시의 번호입니다.
출력
프로그램은 하나의 숫자를 출력해야 합니다. 즉, 건설된 다리의 최소 수이며, 그 후에는 모든 섬에서 다른 섬으로 이동할 수 있습니다.
<몸>
| 입력 |
출력 |
|
4 5
<디브>1 2
1 3
2 3
3 4
<사업부>4 1
|
4 |