27395번 - Toll Roads 다국어

Your state has a number of cities, and the cities are connected by roads. Unfortunately, all of the roads are toll roads!

You now run the local chapter of AAA (American Automobile Association), and people are constantly asking you about the tolls. In particular, they've been asking about individual tolls on any single road on a path between two cities. Odd, but that's what they've been asking!

Given a description of the cities in your state and the roads that connect them, and a series of queries consisting of two separate cities, for each query determine two things:

• First, the smallest value such that there is a route between the two cities where no road has a toll greater than that value.
• Second, the number of cities reachable from your starting city using no road with a toll greater than that first value.

The first line of input contains three integers $n$ ($2 \le n \le 2 \times 10^5$), $m$ ($1 \le m \le 2 \times 10^5$) and $q$ ($1 \le q \le 2 \times 10^5$), where $n$ is the number of cities, $m$ is the number of roads, and $q$ is the number of queries. The cities are each identified by a number $1$ through $n$.

Each of the next $m$ lines contains three integers $u$, $v$ ($1 \le u,v \le n, u \ne v$) and $t$ ($0 \le t \le 2 \times 10^5$), which represents a road between cities $u$ and $v$ with toll $t$. The roads are two-way, and the toll is the same in either direction. It is guaranteed that there is a path between any two cities, and that there is at most one road between any two cities.

Each of the next $q$ lines contains two integers $a$ and $b$ ( $1 \le a,b \le n, a \ne b$). This represents a query about a path from $a$ to $b$.

Output $q$ lines. Each line is an answer to a query, in the order that they appear. Output two space-separated integers, $w$ and $k$, on each line, where $w$ is the smallest amount such that there is a route from $a$ to $b$ with no toll greater that $w$, and $k$ is the number of cities reachable from $a$ using no road with a toll greater than $w$.