The Safest Path#3206
Peter has obtained a map of the city with the pubs marked on it. Peter enjoys visiting pubs, and naturally, he prefers going at night for more excitement. He gets bored sitting in just one pub, so he often visits several pubs in one evening.
Today, Peter has decided to visit two pubs. There are roads between some of the pubs. The roads might be unsafe at night, so Peter has assigned a risk level to each road: the higher the value, the higher the risk. There may not be a direct road between two particular pubs, but a path always exists through other pubs. In this case, the risk of the entire path equals the greatest risk among the roads along the path.
Peter has compiled a list of pairs of pubs he might visit. For each pair, he needs to know the safest path between them. Your task is to help Peter determine, for each pair, the risk of the safest path.
The first line contains three space-separated integers: (1 \leq n \leq 100000, 1 \leq m,\ q \leq 200000) — the number of pubs, the number of roads between them, and the number of pairs to consider.
The next lines describe the roads. Each line contains three space-separated integers: (0 \leq a,\ b < n, 1 \leq c \leq 10000) — two pubs connected by a road and the risk of that road.
The final lines describe the pairs of pubs Peter might visit. Each line contains two space-separated integers: (0 \leq a,\ b < n).
For each pair in Peter's list, output the risk of the safest path between the pubs, with one answer per line.
Example 1