시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 612 160 103 25.945%

문제

어떤 플로우 그래프가 주어졌을때, 한 간선의 용량이 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을 넘지 않는다.

출력

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

예제 입력 1

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

예제 출력 1

3
1
3
W3sicHJvYmxlbV9pZCI6IjU2NTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2NDRcdWM4MDQgXHVjOTExXHVjNjk0XHVkNTVjIFx1YWMwNFx1YzEyMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWI0XHViNWE0IFx1ZDUwY1x1Yjg1Y1x1YzZiMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0XHViNTRjLCBcdWQ1NWMgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzZhOVx1YjdjOVx1Yzc3NCAxXHVjOTA0XHViYTc0IFx1Y2Q1Y1x1YjMwMCBcdWM3MjBcdWI3YzlcdWIzYzQgMVx1Yzc3NCBcdWM5MDRcdWM1YjRcdWI0ZGNcdWIyOTQgXHVhY2JkXHVjNmIwIFx1YWRmOCBcdWFjMDRcdWMxMjBcdWM3NDQgXHVjNjQ0XHVjODA0IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWFjMDRcdWMxMjBcdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LiBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWNiZFx1YzZiMCBcdWM2NDRcdWM4MDQgXHVjOTExXHVjNjk0XHVkNTVjIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHVjNWI0XHViY2Y0XHVjNzkwITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOTA0XHVjOWM0XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggSyAoMSZsdDs9SyZsdDs9MTUpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJm5ic3A7XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWIyOTQgTiwgTSZuYnNwOygyICZsdDs9IE4gJmx0Oz0gMzAwOyAyICZsdDs9IE0gJmx0Oz0gNSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCBcdWFjMDFcdWFjMDEgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWFjMDRcdWMxMjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC4gMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDAgc291cmNlXHViOTdjIE5cdWJjODggXHVjODE1XHVjODEwXHVjNzQwIHNpbmtcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWNcdWIyOTQgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBmLCB0LCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBmXHVjNWQwXHVjMTFjIHRcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWM2YTlcdWI3YzlcdWM3NzQgYigmbHQ7MTAwMClcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjNzIwXHViN2M5XHVjNzU4IFx1ZDU2OVx1Yzc0MCAyMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1Y1x1YzkwNFx1YzUyOSBcdWM2NDRcdWM4MDQgXHVjOTExXHVjNjk0XHVkNTVjIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU2NTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDcnVjaWFsIExpbmtzIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3Ugd291bGQgbGlrZSB0byBicm9hZGNhc3QgdGhlIEFDTSBJQ1BDIFJlZ2lvbmFsIENvbnRlc3QgZXZlbnQgaW4gUGh1a2V0IGluIHJlYWwgdGltZS4gVG8gZG8gc28sIHlvdSBoYXZlIHRvIHRyYW5zbWl0IHRoZSB2aWRlbyBkYXRhIGZyb20gdGhlIHJlY29yZGluZyBtYWNoaW5lIHRvIHRoZSBicm9hZGNhc3Rpbmcgc2VydmVyIGluIEJhbmdrb2suIFlvdSBoYXZlIHRoZSBtYXAgb2YgdGhlIGVudGlyZSBuZXR3b3JrIG9mIFRoYWlsYW5kLiBUaGVyZSBhcmUgTiByb3V0ZXJzIGFuZCBNIG9uZS1kaXJlY3Rpb25hbCBsaW5rcy4gRWFjaCBsaW5rIGksIGZvciAxICZsdDs9IGkgJmx0Oz0gTSwgY2FuIHRyYW5zbWl0IGRhdGEgZnJvbSBSb3V0ZXIgRjxzdWI+aTxcL3N1Yj4gdG8gUm91dGVyIFQ8c3ViPmk8XC9zdWI+LCB3aXRoIGJhbmR3aWR0aCBCPHN1Yj5pPFwvc3ViPi4gSXQgaXMgcG9zc2libGUgdGhhdCB0aGVyZSBhcmUgbW9yZSB0aGFuIG9uZSBsaW5rIHRoYXQgdHJhbnNtaXRzIGRhdGEgZnJvbSBhIHBhcnRpY3VsYXIgcm91dGVyIHRvIGFub3RoZXIgcGFydGljdWxhciByb3V0ZXIuPFwvcD5cclxuXHJcbjxwPlRoZSByZWNvcmRpbmcgbWFjaGluZSBpcyBjb25uZWN0ZWQgdG8gUm91dGVyIDEgd2l0aCBhbiB1bmxpbWl0ZWQtYmFuZHdpZHRoIGxpbmssIGFuZCB0aGUgYnJvYWRjYXN0aW5nIHNlcnZlciBpcyBjb25uZWN0ZWQgdG8gUm91dGVyIE4gYWxzbyB3aXRoIGFuIHVubGltaXRlZC1iYW5kd2lkdGggbGluay48XC9wPlxyXG5cclxuPHA+VG8gdHJhbnNtaXQgdmlkZW8gZGF0YSBmcm9tIFJvdXRlciAxIHRvIFJvdXRlciBOLCB5b3Ugc3BsaXQgdGhlIHZpZGVvIGRhdGEgYW5kIHRyYW5zbWl0IHRoZW0gdXNpbmcgbWFueSB0cmFuc21pc3Npb24gcGF0aHMuIEEgdHJhbnNtaXNzaW9uIHBhdGggaXMgYSBwYXRoIGZyb20gUm91dGVyIDEgdG8gUm91dGVyIE4uIEVhY2ggcGF0aCBjYW4gdHJhbnNtaXQgZGF0YSB3aXRoIHNvbWUgYmFuZHdpZHRoIGIgYW5kIHV0aWxpemUgYmFuZHdpZHRoIGIgZnJvbSBldmVyeSBsaW5rIHVzZWQgYnkgdGhpcyBwYXRoLjxcL3A+XHJcblxyXG48cD5JdCBpcyBwb3NzaWJsZSB0byB1c2UgbWFueSB0cmFuc21pc3Npb24gcGF0aHMgd2l0aCB2YXJpb3VzIGJhbmR3aWR0aHMgYW5kIG1hbnkgcGF0aHMgY2FuIHNoYXJlIGEgbGluay4gSG93ZXZlciwgdGhlIHRvdGFsIGJhbmR3aWR0aCBvZiBhbGwgcGF0aHMgdXNpbmcgYW55IGxpbmsgaSBtdXN0IG5vdCBleGNlZWQgdGhlIGJhbmR3aWR0aCBCPHN1Yj5pPFwvc3ViPi4gVGhlIHRvdGFsIHZpZGVvIGJhbmR3aWR0aCBpcyB0aGUgc3VtIG9mIGFsbCB0cmFuc21pc3Npb24gYmFuZHdpZHRocyBvZiBhbGwgdHJhbnNtaXNzaW9uIHBhdGhzLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbmV0d29yayBtYXAsIHlvdSBjYW4gY2FsY3VsYXRlIHRoZSBiZXN0IHBvc3NpYmxlIHNjaGVtZSB0byBtYXhpbWl6ZSB0aGUgdHJhbnNtaXNzaW9uIGJhbmR3aWR0aCBmcm9tIFJvdXRlciAxIHRvIFJvdXRlciBOLiBIb3dldmVyLCB5b3UgYXJlIGFmcmFpZCB0aGF0IHNvbWUgbGluayBtaWdodCBmYWlsIHRvIHRyYW5zbWl0IGRhdGEgYXMgZmFzdCBhcyB0aGUgY2xhaW1lZCBiYW5kd2lkdGguIEZvciBzb21lIGxpbmsgaSwgaXQgaXMgc3RpbGwgcG9zc2libGUgdG8gb2J0YWluIHRoZSBiZXN0IHRyYW5zbWlzc2lvbiBiYW5kd2lkdGhzIGV2ZW4gd2hlbiB0aGUgbGluayBiYW5kd2lkdGggZHJvcHMgZnJvbSBCPHN1Yj5pPFwvc3ViPiB0byBCPHN1Yj5pPFwvc3ViPiZuZGFzaDsxLiBCdXQgZm9yIHNvbWUgbGluayBpLCBpZiB0aGlzIG9jY3VycywgdGhlIGJlc3QgdmlkZW8gdHJhbnNtaXNzaW9uIGJhbmR3aWR0aCBhbHNvIGRyb3BzOyBjYWxsIHRoaXMgbGluayBhIGNydWNpYWwgbGluay4gTm90ZSB0aGF0IHdoZW4gY29uc2lkZXJpbmcgaWYgYW4gZWRnZSBpIGlzIGNydWNpYWwsIHdlIG9ubHkgY29uc2lkZXIgb25seSBlZGdlIGksIHdoaWxlIGFzc3VtaW5nIHRoYXQgYWxsIGJhbmR3aWR0aHMgb2YgYWxsIG90aGVyIGxpbmtzIHJlbWFpbiB1bmNoYW5nZWQuIGkuZS4sIHdlIGNvbnNpZGVyIGVhY2ggZWRnZSBzZXBhcmF0ZWx5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvbXB1dGUgdGhlIG51bWJlciBvZiBjcnVjaWFsIGxpbmtzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgSywgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzICgxICZsdDs9IEsgJmx0Oz0gMTUpLiBFYWNoIHRlc3QgY2FzZSBpcyBpbiB0aGUgZm9sbG93aW5nIGZvcm1hdC4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgYSBwYWlyIG9mIGludGVnZXJzIE4gYW5kIE0gKDIgJmx0Oz0gTiAmbHQ7PSAzMDA7IDIgJmx0Oz0gTSAmbHQ7PSA1LDAwMCkuIFRoZSBuZXh0IE0gbGluZXMgY29udGFpbiBsaW5rIGluZm9ybWF0aW9uLiBGb3IgMSAmbHQ7PSBpICZsdDs9IE0sIGxpbmUgMSArIGkgY29udGFpbnMgMyBpbnRlZ2VycyBGPHN1Yj5pPFwvc3ViPiwgVDxzdWI+aTxcL3N1Yj4sIGFuZCBCPHN1Yj5pPFwvc3ViPiAoMSAmbHQ7PSBGPHN1Yj5pPFwvc3ViPiAmbHQ7PSBOOyAxICZsdDs9IFQ8c3ViPmk8XC9zdWI+ICZsdDs9IE47IDEgJmx0Oz0gQjxzdWI+aTxcL3N1Yj4gJmx0Oz0gMSwwMDApLiBUaGUgc3VtIG9mIGFsbCBiYW5kd2lkdGhzIEI8c3ViPmk8XC9zdWI+IGlzIGF0IG1vc3QgMjAsMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBtdXN0IG91dHB1dCBLIGludGVnZXJzLCBlYWNoIG9uIGEgc2VwYXJhdGUgbGluZS4gRm9yIGVhY2ggdGVzdCBjYXNlLCB5b3VyIHByb2dyYW0gbXVzdCBvdXRwdXQgdGhlIG51bWJlciBvZiBjcnVjaWFsIGxpbmtzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==