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

#5944

단절쌍 3초 1024MB

문제

[원문]

When Leonhard Euler resolved the famous Königsberg bridge problem, he had no clue he had discovered a whole new area of mathematics - graph theory!

Unfortunately, the Königsberg bridge problem is far too easy for the programmers of this era, so Euler came up with another problem - the Zagreb bridge problem!

The bridges of Zagreb form a graph with n nodes and m edges where the edges represent the bridges and the nodes represent the riverine islands. The graph is connected, in other words, it’s possible to get from any node to any other by traveling across the edges. Now Euler asked, how many edges are there such that after their removal the graph becomes disconnected?

Again, Euler didn’t know that this problem is also famous today (those damn Codeforces blogs). So the author of this problem decided to give you an even harder one, how many edges are there such that after the removal of the nodes which it connects, the remaining n − 2 nodes become disconnected?

[번역]

스위스 출신 천재 수학자 레온하르트 오일러가 유명한 쾨니히스베르크의 다리 문제를 해결했을 때, 그는 수학의 완전히 새로운 영역, 즉 그래프 이론을 발견했습니다!

불행히도 쾨니히스베르크의 다리 문제는 이 시대의 프로그래머에게는 너무 쉽기 때문에 오일러는 또 다른 문제인 자그레브 다리 문제를 생각해 냈습니다!

자그레브 다리는 n개의 노드와 m개의 간선을 갖는 그래프를 형성합니다. 여기서 간선은 다리를 나타내고 노드는 강변 섬을 나타냅니다. 그래프는 연결되어 있습니다. 다른 말로 모든 노드에서 다른 모든 노드로 이동하는 것이 가능합니다. 이제 오일러는 간선을 제거한 후 그래프의 연결이 끊어지는 간선이 몇 개 있는지 물었습니다.

안타깝게도 오일러는 이 문제도 오늘날에 유명하다는 사실을 몰랐습니다. 그래서 이 문제의 저자는 더 어려운 문제를 주기로 결정했습니다. 간선을 제거할 때, 해당 간선에 연결된 두 노드를 함께 제거한 후 나머지 n − 2개 노드의 연결이 끊어지는 간선이 몇 개 있습니까?


입력

[원문]

The first line contains integers n and m (4 ≤ n ≤ 100 000, n − 1 ≤ m ≤ 300 000) - the number of nodes and edges respectively.

Each of the next m lines contains integers ai and bi (1 ≤ ai, bi ≤ n) - this means nodes ai and bi are connected with an edge.

There are no loops or multiple edges.

[번역]

첫 줄에 노드의 수와 간선의 수를 뜻하는 두 정수 n과 m이 주어진다, (4 ≤ n ≤ 100\ 000, n − 1 ≤ m ≤ 300\ 000)

이어 m줄에 걸쳐 i번째 줄에 간선으로 이어진 두 노드 a_i와 b_i가 주어진다. (1 ≤ a_i, b_i ≤ n, a_i \neq b_i)

중복되는 간선이 없음이 보장된다.


출력

[원문]

In a single line output the number of edges with the given property.

[번역]

첫 줄에 연결된 노드를 제거한 후 나머지 n − 2개 노드의 연결이 끊어지는 간선의 수를 출력한다.


부분문제

번호 점수 조건
#113점

n ≤ 100, m ≤ 300

#217점

n ≤ 1\ 000, m ≤ 3\ 000

#325점

n ≤ 1\ 000

#412점

m − n ≤ 20

#533점

추가 제한 없음


예제1

입력
45
12
23
34
41
13
출력
1

[원문]

By removing edge (1, 3) and corresponding nodes 1 and 1, the remaining graph has two connected components, node 2 and node 4. In other words, it is not connected. It is easy to check it is the only edge with this property.

[번역]

간선 (1,3)과 이에 연결된 노드 1과 3을 지우게 되면 각각 (노드 2)와 (노드 4)로만 이루어진 두 개의 분리된 그래프가 됩니다.


예제2

입력
67
12
24
26
35
61
43
25
출력
4

[원문]

The edges with the given property are (1, 2), (2, 4), (2, 6) abd (2, 5).

[번역]

답이 될 수 있는 간선: (1, 2), (2, 4), (2, 6), (2, 5).


출처

COCI 2023/2024 Contest #1 5번

역링크