Totally Important Edges

Time limit1sMemory limit256 MB

Summary
Given a directed flow network, count the edges whose capacity decrease by 1 lowers the maximum flow by exactly 1.
Level

Hard8 of 10

Topics
Graph, Shortest path, Dynamic programming
Solved
No attempts yet

Problem

A directed flow graph is given. If decreasing the capacity of some edge by 11 also decreases the graph's maximum flow by exactly 11, that edge is called a totally important edge.

Given the graph, count the number of totally important edges.

Input

The input consists of several test cases.

The first line contains the number of test cases KK (1≤K≤151 \le K \le 15).

For each test case, the first line contains the number of vertices NN and the number of edges MM (2≤N≤3002 \le N \le 300, 2≤M≤5,0002 \le M \le 5{,}000). Vertex 11 is the source and vertex NN is the sink.

Each of the next MM lines contains three integers ff, tt, and bb, describing an edge from vertex ff to vertex tt with capacity bb (b<1000b < 1000). The sum of all edge capacities does not exceed 20,00020{,}000.

Output

For each test case, print the number of totally important edges on its own line.

Examples2

  1. Example 1

    Input
    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
    Expected output
    3
1
3

  2. Example 2

    Input
    1
2 2
1 2 5
1 2 3
    Expected output
    2