페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7037

단절선 구하기 3s 1024MB

문제

정점이 N개, 간선이 M개인 연결그래프가 주어진다.

정점 u와 v를 잇는 간선에 대해, 전체 그래프에서 정점 u와 v, 그리고 u와 v에 연결된 모든 간선을 삭제했을 때 전체 그래프가 연결되어 있지 않도록 하는 간선의 개수를 구하여라.


입력

첫 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (4<=N<=100000, N-1<=M<=300000)

그 다음 M줄에 걸쳐 각 간선에 대한 정보 u, v가 공백으로 구분되어 주어진다. (1<=u, v<=N)

이때 자기 자신으로 향하는 간선이나, 같은 정점 쌍 사이 중복된 간선은 주어지지 않는다.


출력

조건을 만족하는 간선의 개수를 한 줄에 출력하시오.


부분문제

번호 점수 조건
#113점

N<=100, M<=300

#217점

N<=1000, M<=3000

#325점

N<=1000

#412점

M-N<=20

#543점

제한 없음


예제 #1

4 5
1 2
2 3
3 4
4 1
1 3
1

간선 (1, 3)을 제거하면 그래프가 정점 2/정점 4 로 나뉜다.


예제 #2

6 7
1 2
2 4
2 6
3 5
6 1
4 3
2 5
4

(1, 2), (2, 4), (2, 6), (2, 5)가 조건을 만족하는 간선들이다.


출처

COCI 2023/2024 Contest #1
로그인해야 코드를 작성할 수 있어요.