Description

Xiaobai learned a new concept—minimum cut—in a graph theory class. After class, Xiaobai wrote the following in the notebook:

For a graph, a partition of the vertices divides all vertices into two parts. If vertices $s$ and $t$ are not in the same part, then this partition is called a cut with respect to $s,t$. For a weighted graph, the sum of the weights of all edges whose endpoints lie in different parts is defined as the capacity of this cut, and the minimum cut of $s,t$ is the cut with the minimum capacity among all cuts with respect to $s,t$.

Given an undirected graph, Xiaobai has several questions of the form “how many unordered pairs of vertices have minimum-cut capacity not exceeding $x$”. Xiaolan would like to answer these questions but is currently busy mining wooden blocks, so as Xiaolan’s friend, the task falls on you.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains two integers $n,m$, the number of vertices and edges.

The next $m$ lines each contain three integers $u,v,c$, indicating an undirected edge $(u,v)$ with weight $c$. Multiple edges are allowed.

Then a line with an integer $q$ follows, the number of queries. Each of the next $q$ lines contains an integer $x$ describing one query.

Output Format

For each test case, output $q$ lines, each containing one integer: the answer to the corresponding query. For a qualifying pair $(p,q)$ and the pair $(q,p)$, count only once.

Output one empty line between two consecutive test cases.

1
5 0
1
0

10

Hint

For $100\%$ of the testdata, $1 \leq T \leq 10$, $1 \leq n \leq 150$, $0 \leq m \leq 3000$, $0 \leq x \leq 2^{31}-1$, $0 \leq q \leq 30$, $1 \leq u,v \leq n$, $0 \leq c \leq 10^6$.

Translated by ChatGPT 5