题目描述

Bitimaa 由 $N$ 座城市组成，编号为 $1,2,\ldots,N$。城市之间有 $M$ 条双向公路，每条公路直接连接两座城市，中间没有其他停靠点。

已知：

• 没有公路连接一座城市自身；
• 不存在两条不同公路连接同一对城市；
• 通过这些公路，可以从任意城市到达任意其他城市。

Juku 住在城市 $1$。沿一条公路行走需要 1 小时。

此外，Juku 拥有一个强大的传送器。但是这个传送器坏了：每次使用传送器后，Juku 会以均匀随机的方式出现在某座城市。也就是说，对每座城市而言，传送后 Juku 出现在该城市的概率都是 $\frac{1}{N}$。传送器也可能让 Juku 留在原地。

传送器的架设是一项复杂且耗时的技术工作：每次 Juku 想使用传送器时，都需要花费 $K$ 小时。

请你对每个城市 $u$（$2 \le u \le N$），求出在 Juku 做出最优选择的前提下，从城市 $u$ 到城市 $1$ 平均需要多少时间。

可以证明，在本题限制下，每个 $u$ 对应的期望值都可以表示成分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，并且满足：

$$0 \le p \le 10^{18},\quad 1 \le q \le 10^{18}.$$

输入格式

第一行包含三个整数 $N,M,K$。

接下来 $M$ 行，每行包含两个整数 $A$ 和 $B$，表示城市 $A$ 与城市 $B$ 之间有一条双向公路。

输出格式

输出 $N-1$ 行。

其中第 $i$ 行输出两个整数 $p$ 和 $q$，表示从城市 $i+1$ 到城市 $1$，在最优选择下平均需要 $\frac{p}{q}$ 小时。

输出的分数不需要化简。

样例 1

输入

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

输出

1 1
9 4
1 1
2 1

样例解释

可以证明，如果 Juku 从城市 3 出发，最优策略是不断使用传送器，直到他传送到某个不同的城市，然后再沿公路移动。如果 Juku 从其他城市出发，则最优策略是只沿公路移动。

考虑 Juku 从城市 3 出发的情况。第一次传送就到达某座其他城市的概率为 $\frac45$；第二次才成功的概率为 $\frac15\cdot\frac45$；第三次才成功的概率为 $\frac15\cdot\frac15\cdot\frac45$；依此类推。

因此，传送尝试次数的期望为：

$$1\cdot\frac45+2\cdot\frac15\cdot\frac45+3\cdot\frac15\cdot\frac15\cdot\frac45+\cdots=1.25.$$

成功传送到其他城市之后：

• 有 $\frac14$ 的概率在城市 1，不需要再移动；
• 有 $\frac12$ 的概率在城市 2 或城市 4，从任一城市都需要再走 1 条公路；
• 有 $\frac14$ 的概率在城市 5，需要再走 2 条公路。

所以总期望时间为：

$$1.25+\frac14\cdot0+\frac12\cdot1+\frac14\cdot2=2.25=\frac94.$$

样例 2

输入

6 9 100
3 4
3 2
6 5
3 6
6 1
6 4
5 4
5 1
2 1

输出

1 1
2 1
2 1
1 1
1 1

样例解释

本例中，传送非常昂贵，因此 Juku 总是沿公路行走才是合理的。

样例 3

输入

15 17 3
14 7
13 6
14 10
1 7
2 12
4 12
4 5
6 10
15 2
13 4
12 15
8 2
9 11
13 10
5 2
2 11
3 9

输出

7 1
318 39
5 1
78 13
2892 723
1 1
8 1
4982 611
3 1
8 1
6 1
5348 1337
2 1
14 2

样例解释

请注意，输出中的分数不需要化简。例如最后一行的分数 $\frac{14}{2}$ 与 $\frac71$ 相同。

数据范围与评分

对于所有数据：

$$1 \le N,M,K \le 3\cdot10^5,$$ $$1 \le A,B \le N,\quad A \ne B.$$

测试点分为以下组。只有通过某组内所有测试点，才能获得该组分数：

1. $N=K$，20 分；
2. $N \le 20$，20 分；
3. $N,M \le 10^3$，20 分；
4. 无额外限制，40 分。