ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
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

ログインしないとコードを書けません。