$C$ 国共有 $n$ 座城市，编号为 $0 \sim n - 1$。这 $n$ 座城市由 $n - 1$ 条道路连接，形成一棵树。第 $i \ (0 \le i < n - 1)$ 条道路连接城市 $u_i$ 和城市 $v_i$，从道路的一端到达另一端需要花费 $1$ 单位时间。

为了提升通行效率，$C$ 国研发了一种新型传送门。每座城市中均有一扇传送门。使用传送门同样需要花费 $1$ 单位时间，但由于系统尚不稳定，传送门会将使用者等概率地传送到所有 $n$ 座城市之一。

注意：使用传送门也可能被传送到当前所在的城市。

为了测试传送门的效果，$C$ 国进行了 $m$ 次测试。第 $i \ (0 \le i < m)$ 次测试要求测试员从城市 $x_i$ 出发，前往城市 $y_i$。在从起点前往终点的过程中，测试员可以选择沿道路移动，也可以使用传送门。测试员希望选择一种期望耗时最短的通行方式。

具体地，对于一次终点为城市 $y_i$ 的测试，一种通行方式需要为每座非终点城市预先确定一种行动：移动到某座与其相邻的城市，或使用传送门。每当测试员到达这座城市时，均按照预先确定的行动进行移动。

形式化地，一种通行方式可以用一个长度为 $n$ 的序列 $[a_0,a_1,\dots,a_{n - 1}]$ 表示，其中 $a_{y_i} = -1$，并且对于所有 $j \ne y_i$，满足以下两个条件之一：

• $a_j$ 是一座与城市 $j$ 相邻的城市；
• $a_j = n$。

每当测试员到达城市 $j \ (j \ne y_i)$ 时：

• 若 $a_j < n$，则测试员沿道路移动到城市 $a_j$；
• 若 $a_j = n$，则测试员使用传送门。

称一种通行方式是合理的，当且仅当使用这种通行方式到达终点的期望耗时为有限值。

对于每次测试，请计算所有合理通行方式中，期望耗时的最小值。

实现细节

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序源文件包含头文件 teleport.h，即在程序开头加入以下代码：

#include "teleport.h"

选手需要在提交的程序源文件 teleport.cpp 中实现以下函数：

std::vector<std::pair<long long, int>> teleport(int c, int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> x, std::vector<int> y);

• $c,n,m$ 分别表示测试点编号、城市数量和测试次数。$c = 0$ 表示该测试点为样例。
• $u,v$ 均为长度为 $n - 1$ 的序列，其中 $u_i,v_i \ (0 \le i < n - 1)$ 表示第 $i$ 条道路连接的两座城市。
• $x,y$ 均为长度为 $m$ 的序列，其中 $x_i,y_i \ (0 \le i < m)$ 分别表示第 $i$ 次测试的起点与终点。
• 该函数需要返回一个长度恰好为 $m$ 的二元组序列 $[(a_0,b_0),(a_1,b_1),\dots,(a_{m - 1},b_{m - 1})]$。
• 对于每个 $0 \le i < m$，若第 $i$ 次测试中期望耗时的最小值写成最简分数为 $\frac{a_i}{b_i}$，则返回序列中的第 $i$ 个二元组应为 $(a_i,b_i)$。
• 特别地，若期望耗时的最小值为正整数，则应令 $b_i = 1$。
• 对于每个测试点，该函数会被评测程序调用恰好一次。

本试题目录下的 template_teleport.cpp 是提供的示例代码，选手可参考并实现自己的代码。

测试程序方式

选手可以在本题目录下使用如下命令编译得到可执行文件：

g++ grader.cpp teleport.cpp -o teleport -O2 -std=c++14 -static

对于编译得到的可执行文件 teleport：

• 可执行文件将从标准输入读入以下格式的数据：

  • 第一行包含三个非负整数 $c,n,m$。
  • 接下来 $n - 1$ 行，第 $i + 1 \ (0 \le i < n - 1)$ 行包含两个非负整数 $u_i,v_i$。
  • 接下来 $m$ 行，第 $i + 1 \ (0 \le i < m)$ 行包含两个非负整数 $x_i,y_i$。

• 可执行文件将输出以下格式的数据至标准输出：

  • 共输出 $m$ 行，第 $i + 1 \ (0 \le i < m)$ 行包含两个正整数 $a_i,b_i$。

样例一

input

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

output

7 3
1 1
2 1
1 1

explanation

对于第 $0$ 次测试：

• 若通行方式为 $[1,2,3,-1]$，则测试员依次经过城市 $0,1,2,3$，耗时恒为 $3$。
• 若通行方式为 $[4,2,3,-1]$，则测试员会在城市 $0$ 不断使用传送门，直至被传送到城市 $1,2,3$ 中的一座。该通行方式的期望耗时为 $\frac{7}{3}$。
• 若通行方式为 $[4,4,3,-1]$，则测试员会不断使用传送门，直至到达城市 $2$ 或城市 $3$。该通行方式的期望耗时为 $3$。
• 若通行方式为 $[1,0,4,-1]$，则测试员将永远在城市 $0$ 与城市 $1$ 之间移动，因此该通行方式不是合理的。

可以证明，所有合理通行方式中，期望耗时的最小值为 $\frac{7}{3}$。

样例二

见下发文件 teleport/teleport2.in 与 teleport/teleport2.ans。

该样例满足测试点 $2,3$ 的约束条件。

样例三

见下发文件 teleport/teleport3.in 与 teleport/teleport3.ans。

该样例满足测试点 $4 \sim 6$ 的约束条件。

样例四

见下发文件 teleport/teleport4.in 与 teleport/teleport4.ans。

该样例满足测试点 $7,8$ 的约束条件。

样例五

见下发文件 teleport/teleport5.in 与 teleport/teleport5.ans。

该样例满足测试点 $9$ 的约束条件。

样例六

见下发文件 teleport/teleport6.in 与 teleport/teleport6.ans。

该样例满足测试点 $16$ 的约束条件。

样例七

见下发文件 teleport/teleport7.in 与 teleport/teleport7.ans。

该样例满足测试点 $17 \sim 20$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $2 \le n \le 5 \times 10^5$；
• $1 \le m \le 10^6$；
• 对于所有 $0 \le i < n - 1$，均有 $0 \le u_i,v_i < n$，且所有道路 $(u_i,v_i)$ 构成一棵树；
• 对于所有 $0 \le i < m$，均有 $0 \le x_i,y_i < n$ 且 $x_i \ne y_i$。

特殊性质 A：对于所有 $0 \le i < n - 1$，均有 $u_i = i$ 且 $v_i = i + 1$。

特殊性质 B：对于所有 $0 \le i < m$，均有 $y_i = 0$。

时间限制：$\texttt{3.5s}$

空间限制：$\texttt{1GB}$