题目描述

给定一个 $n$ 个点， $m-1$ 条边的无向连通图。其中这些边的权值是 $2 \sim m$ 的一个置换。

我们称一条路径的权值为它上面边权的乘积。试问， $s$ 到 $t$ 的路径权值可以在不超过 $m$ 的情况 下最大达到多大?

注意，这里的路径可以反复经过一个点或一条边。

你需要回答多组询问。

输入格式

第一行输入三个正整数 $n, m, q$ 。 接下来 $m-1$ 行每行输入两个正整数 $u, v$ ，分别表示边权为 $2,3, \ldots, m$ 的那条边所连接的两个 点。

注意图可能含有重边和自环。

接下来 $q$ 行每行两个正整数 $s, t$ ，表示一组询问。

输出格式

输出 $q$ 行，每行一个数，如果存在权值不超过 $m$ 的路径则输出其中的最大值，否则输出 -1 。

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

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

说明/提示

本题输入输出范围较大，请使用较快的读入输出方式。

数据规模与约定

对于 $100 \%$ 的数据，保证 $2 \leq n \leq m \leq 5 \times 10^5 ， 1 \leq q \leq 5 \times 10^5$ 。

• Subtask 1 (10 pts) : 保证 $m \leq 10$ 。
• Subtask 2 (10 pts) : 保证 $m \leq 100$ 。
• Subtask 3 (20 pts) : 保证 $m \leq 10^3$ 。
• Subtask 4 (20 pts) : 保证 $m \leq 10^4$ 。
• Subtask 5 (30 pts) : 保证 $m \leq 10^5$ 。
• Subtask 6 (10 pts)：无特殊限制。

大样例

大样例下载