408476: GYM103145 K City

Lucida occupies $$$n$$$ cities connected by $$$m$$$ undirected roads, and each road has a strength $$$k_i$$$. The enemy will attack to destroy these roads. When the enemy launches an attack with damage $$$x$$$, all roads with strength less than $$$x$$$ will be destroyed.

Now Lucida has $$$Q$$$ questions to ask you, how many pairs of cities are reachable to each other if the enemy launches an attack with damage $$$p_i$$$. City $$$x$$$ and city $$$y$$$ are reachable, which means that there is a path from $$$x$$$ to $$$y$$$, and every road's strength in that path is greater than or equal to $$$p_i$$$.

This problem contains multiple test cases.

The first line contains a single integer $$$T$$$ ($$$1\leq T \leq 10$$$).

Then $$$T$$$ test cases follow.

For each test case, the first line contains 3 integers $$$n, m, Q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq 2 \times 10^5$$$, $$$1 \leq Q \leq 2 \times 10^5$$$), which represent the number of cities, the number of roads, and the number of queries.

The next $$$m$$$ lines, each line contains three integers $$$x, y, k$$$ ($$$1 \leq x, y \leq n$$$, $$$1 \leq k \leq 10^9$$$), which represent the road connecting city $$$x$$$ and city $$$y$$$, and the strength of this road is $$$k$$$.

The next $$$Q$$$ lines, each line contains an integer $$$p_i$$$ ($$$1 \leq p_i \leq 10^9$$$), asking how many pairs of cities are reachable to each other if the enemy launches an attack with damage $$$p_i$$$.

Output $$$\sum_{1}^{T} Q$$$ lines, each line contains an integer, representing the answer for each question.

1
5 5 3
1 2 2
2 3 3
3 4 1
4 5 1
5 1 3
3
2
1

2
6
10