题目描述

一个州有若干城市，城市之间由道路连接。不幸的是，所有道路都是收费公路。

你负责当地 AAA（美国汽车协会）分会，经常有人询问关于收费的问题。具体来说，他们会给出两个城市，询问从一个城市到另一个城市时，路径上单条道路收费的情况。

给定城市和道路信息，以及若干查询。对于每个查询 $(a,b)$，你需要确定两个值：

1. $w$：使得存在一条从 $a$ 到 $b$ 的路径，且路径上所有道路的收费都不超过 $w$ 的最小值；
2. $k$：在只允许使用收费不超过 $w$ 的道路时，从起点 $a$ 能到达的城市数量。

输入格式

第一行包含三个整数 $n,m,q$：

$$2\le n\le 2\times 10^5,\qquad 1\le m\le 2\times 10^5,\qquad 1\le q\le 2\times 10^5.$$

其中 $n$ 是城市数量，$m$ 是道路数量，$q$ 是查询数量。城市编号为 $1$ 到 $n$。

接下来 $m$ 行，每行包含三个整数 $u,v,t$：

$$1\le u,v\le n,\quad u\ne v,\quad 0\le t\le 2\times 10^5.$$

表示城市 $u$ 和 $v$ 之间有一条双向道路，收费为 $t$。

保证：

• 任意两个城市之间都存在路径；
• 任意两座城市之间最多只有一条道路。

接下来 $q$ 行，每行包含两个整数 $a,b$，表示一次从 $a$ 到 $b$ 的查询：

$$1\le a,b\le n, \qquad a\ne b.$$

输出格式

输出 $q$ 行，按输入顺序回答每个查询。

每行输出两个空格分隔的整数 $w,k$，其中：

• $w$ 是从 $a$ 到 $b$ 的最小可能最大边权；
• $k$ 是只使用收费不超过 $w$ 的道路时，从 $a$ 能到达的城市数量。

样例 #1

输入

4 3 6
1 2 1
2 3 3
3 4 2
1 2
1 3
1 4
2 3
2 4
3 4

输出

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

数据范围

$$2\le n,m,q\le 2\times 10^5, \qquad 0\le t\le 2\times 10^5.$$