dgeu-learning
Time limit4sMemory limit512 MB
Given a connected weighted graph, answer queries for the maximum bottleneck path value between pairs of vertices.
- Level
Medium7 of 10
- Topics
- Minimum spanning tree, Union-find, Sorting, Graph
- Solved
- No attempts yet
Problem
Daegu Science High School has a Wi-Fi network called dgeu-learning. In exchange, the Daegu Metropolitan Office of Education forcibly installs the naePC security check program on every computer. On top of that, the speed is terrible! In the end, Daun, fed up with using the study program league of legends over dgeu-learning, decides to build his own internet system.
Daun first connects N computers (numbered 1 through N) with a total of M LAN cables. A LAN cable lets the two computers it connects transmit data freely. The LAN cables have various data transfer speeds, and all computers are connected directly or indirectly through LAN cables. Daun first decides to experiment with P2P communication (communication between computers).
Consider two computers A and B (A≠B) exchanging data with each other. A path made of LAN cables connecting A and B always exists. The data transfer speed over a path is the minimum of the transfer speeds of the LAN cables that make up that path. If there are several paths connecting A and B, the internet system Daun built automatically chooses the path that gives the highest transfer speed.
To test whether his system works well, Daun will repeatedly pick two computers and measure the data transfer speed. Compute how much communication speed Daun's system should produce if it works correctly.
Input
The first line gives the number of computers N in the system Daun built, the number of LAN cables M, and the number of tests Q Daun will perform. (2 ≤ N ≤ 200,000, N - 1 ≤ M ≤ 500,000, 1 ≤ Q ≤ 200,000)
Each of the next M lines gives three integers separated by spaces: the numbers A and B of the two computers the LAN cable connects, and the communication speed V. (1 ≤ A, B ≤ N, A ≠ B, 1 ≤ V ≤ 10^9) Note that the same pair A, B can appear several times, meaning there are several LAN cables connecting A and B.
The following Q lines give the numbers A and B of the two computers whose data transfer speed Daun will test. (1 ≤ A, B ≤ N, A ≠ B)
Output
For each of the Q lines, output in order the value computed as the data transfer speed between the two computers A and B.