문제1374--브릿지 세기

1374: 브릿지 세기

실행시간 제한: 4 Sec  메모리사용 제한: 128 MB
제출: 210  통과: 67
[제출] [채점기록] [묻고답하기]

문제 설명

그래프에서 어떤 간선이 브릿지라 함은, 그 간선을 그래프에서 제거했을 때 정점 간의 연결성이 바뀐다는 뜻이다.

주어진 그래프에서 브릿지가 모두 몇 개인지 세는 프로그램을 작성하라.

입력 설명

입력은 여러 개의 테스트 케이스로 구성된다. 첫 행에는 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 행에는 두 정수 V, E가 주어진다. V는 정점의 수로 100 이하이고, E는 간선의 수로 10000 이하이다.

다음 E 개의 행에 걸쳐 간선의 양 끝 인덱스가 공백으로 구분되어 주어진다. 각 인덱스는 0부터 센다.

중복된 간선은 주어지지 않는다.

출력 설명

각 테스트 케이스에 대해 한 행에 하나씩 답안을 출력한다.

입력 예시 Copy

1
3 2
0 1
1 2

출력 예시 Copy

2

출처/분류