Informatica Online Judge

  전압 [1040 / 0410]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 4   Total Tried : 14


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JOI 2014 Spring Camp]

Background

물리를 좋아하는 경곽이는 물리 실험실에서 복잡한 회로를 다루고 있다.

이 회로는 N개의 정점과 M개의 작은 저항으로 구성되며, 각 정점은 1부터 N까지의 번호가 있다.

각 정점은 "고전압" 또는 "저전압" 중 하나로 설정할 수 있다.

각 저항은 2개의 정점을 연결하고 있으며, 각각의 정점의 한쪽이 "고전압", 다른 한쪽이 "저전압"의 상태일 때, 전류가 흐른다.

"고전압"인 정점끼리, 또는 "저전압"의 정점끼리 연결된 저항은 전류가 흐르지 않는다.

어느 날, 경곽이는 회로의 1개의 저항을 골라서, 그 저항만 준류가 흐르지 않고, 남은 M-1개의 저항에 전류가 흐르도록, 각 정점의 전압을 설정하려고 한다.

이렇게 설정하기 위하여 전류가 흐르지 않도록 할 수 있는 저항은 몇 개나 되는지 궁금해졌다. 이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 N, M이 공백으로 구분되어 입력된다.
두 번째 줄부터 M줄에 걸쳐서 각 저항이 연결된 정점의 정보 a, b가 공백으로 구분되어 입력된다. (단, 같은 정점을 연결하는 경우는 없으나, 여러 개의 저항이 두 정점을 연결할 수 있으며, 모든 회로는 연결되지 않았을 수도 있다.)

[입력값의 정의역]
2 <= N <= 100,000
1 <= M <= 200,000

[Sub-Task Info]
#1 : N <= 1,000; M <= 2,000
#2 : M = N (연결 그래프임이 보장된다.)
#3 : M <= N + 100 (연결 그래프임이 보장된다.)
#4 : 추가 제한 조건은 없다.

Output

경곽이가 문제의 조건을 만족시킬 수 있도록 고를 수 있는 저항의 수를 출력한다.

IO Example

입력
4 5
1 2
1 3
1 4
2 4
3 4

출력
1

* 설명 :
위 예시에서는 3번 저항만 전류를 흐르지 않도록 할 수 있다. 예를 들어 정점 1과 정점 4를 고전압으로 정점 2와 2정점 3을 저전압으로 설정하면 된다. 3번 저항은 정점 1과 정점 4를 연결하고 있으므로 3번 저항은 전기를 흘리지 않는다.



입력2
4 4
1 2
2 3
3 2
4 3

출력2
2

* 설명 :
이 예는 1번 저항 또는 4번 저항을 전기를 흐르지 않도록 할 수 있다.



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]