시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 53 18 15 40.541%

문제

어떤 플로우 그래프가 주어졌을때, 한 간선의 용량이 1줄면 최대 유량도 1이 줄어드는 경우 그 간선을 완전 중요한 간선이라고 부른다. 그래프가 주어진 경우 완전 중요한 간선의 개수를 세어보자!

입력

입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1<=K<=15)가 주어진다.  각 테스트 케이스에는 N, M (2 <= N <= 300; 2 <= M <= 5,000)가 주어지고 각각 정점의 수와 간선의 수를 뜻한다. 1번 정점은 source를 N번 정점은 sink를 뜻한다. 

다음 M줄에 걸쳐서는 세개의 정수 f, t, b가 주어지는데 f에서 t로 가는 간선의 용량이 b(<1000)라는 뜻이다. 모든 유량의 합은 20,000을 넘지 않는다.

출력

각 테스트케이스마다 한줄씩 완전 중요한 간선의 수를 출력한다.

예제 입력

3
2 3
1 2 10
1 2 5
1 2 7
4 3
1 2 10
2 3 5
3 4 6
5 7
1 2 2
1 3 3
2 3 10
3 2 10
3 4 4
2 4 2
4 5 5

예제 출력

3
1
3

힌트