#1374 브릿지 세기

45  4 s   128 MB  

Description

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

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

Input

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

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

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

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

Output

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

Sample Input

Sample Output

1
3 2
0 1
1 2
2