유료 도로

나라에는 여러 도시가 있고, 도시들은 도로로 연결되어 있다. 안타깝게도 모든 도로가 유료 도로다.

당신은 AAA(American Automobile Association) 지역 지부를 운영한다. 사람들은 통행료에 관해 계속 묻는데, 특히 두 도시를 잇는 경로 위에 있는 개별 도로의 통행료를 묻는다. 이상하지만 실제로 그렇게 묻고 있다.

도시와 도로 정보, 그리고 각각 두 도시로 이루어진 질의들이 주어진다. 각 질의마다 다음 두 가지를 구한다.

• 첫째, 두 도시 사이에 경로가 존재하면서 그 경로의 어떤 도로도 통행료가 $w$보다 크지 않도록 하는 가장 작은 $w$ 값.
• 둘째, 출발 도시에서 통행료가 $w$보다 큰 도로를 한 번도 쓰지 않고 도달할 수 있는 도시의 수.

첫 줄에 세 정수 $n$ ($2 \le n \le 2 \times 10^5$), $m$ ($1 \le m \le 2 \times 10^5$), $q$ ($1 \le q \le 2 \times 10^5$)이 주어진다. $n$은 도시의 수, $m$은 도로의 수, $q$는 질의의 수다. 도시에는 1부터 $n$까지 번호가 붙어 있다.

이어지는 $m$개의 줄에는 세 정수 $u$, $v$ ($1 \le u, v \le n$, $u \ne v$)와 $t$ ($0 \le t \le 2 \times 10^5$)가 주어진다. 이는 도시 $u$와 $v$를 잇는 통행료 $t$의 도로를 뜻한다. 도로는 양방향이며, 양방향 통행료는 같다. 임의의 두 도시 사이에는 경로가 있고, 두 도시를 잇는 도로는 최대 하나다.

이어지는 $q$개의 줄에는 두 정수 $a$, $b$ ($1 \le a, b \le n$, $a \ne b$)가 주어진다. 이는 $a$에서 $b$로 가는 경로에 관한 질의다.

$q$개의 줄을 출력한다. 각 줄은 질의 순서대로 하나의 답이다. 각 줄에는 공백으로 구분된 두 정수 $w$와 $k$를 출력한다. $w$는 통행료가 $w$보다 크지 않은 $a$에서 $b$로 가는 경로가 존재하는 가장 작은 값이고, $k$는 통행료가 $w$보다 큰 도로를 쓰지 않고 $a$에서 도달할 수 있는 도시의 수다.