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

我们称一条路径的权值为它上面边权的乘积。试问，$s$ 到 $t$ 的路径权值可以在不超过 $m$ 的情况下最大达到多大？ 注意，这里的路径可以反复经过一个点或一条边。

你需要回答多组询问。

输入格式

第一行输入三个正整数 $n,m,q$。

接下来 $m-1$ 行每行输入两个正整数 $u,v$，分别表示边权为 $2,3,\dots, 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$。

对于数据点 $1$，保证 $m\leq 10$。

对于数据点 $2$，保证 $m\leq 100$。

对于数据点 $3\sim 4$，保证 $m\leq 10^3$。

对于数据点 $5\sim 6$，保证 $m\leq 10^4$。

对于数据点 $7\sim 9$，保证 $m\leq 10^5$。

对于数据点 $10$，无特殊限制。

提示

本题输入输出范围较大，可能需要使用 IO 优化，提供如下模板，并注意注释处是文件 IO 的开启位置：

using u32 = unsigned;
struct IO_Tp
{
    const static int _I_Buffer_Size = 30 << 20;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;

    const static int _O_Buffer_Size = 8 << 20;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    u32 m[10000];

    IO_Tp()
    {
//        freopen("tour.in", "r", stdin);
//        freopen("tour.out", "w", stdout);
        constexpr u32 e0 = '\0\0\0\1', e1 = '\0\0\1\0', e2 = '\0\1\0\0', e3 = '\1\0\0\0';
        int x = 0;
        for (u32 i = 0, c0 = '0000'; i != 10; ++i, c0 += e0)
            for (u32 j = 0, c1 = c0; j != 10; ++j, c1 += e1)
                for (u32 k = 0, c2 = c1; k != 10; ++k, c2 += e2)
                    for (u32 l = 0, c3 = c2; l != 10; ++l, c3 += e3)
                        m[x++] = c3;

        fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
    }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(int &res)
    {
        while (!isdigit(*_I_pos))
            ++_I_pos;
        res = *_I_pos++ - '0';
        while (isdigit(*_I_pos))
            res = res * 10 + (*_I_pos++ - '0');
        return *this;
    }

    IO_Tp &operator<<(int x)
    {
        if (x == -1)
        {
            *_O_pos++ = '-';
            *_O_pos++ = '1';
            return *this;
        }
        if (x == 0)
        {
            *_O_pos++ = '0';
            return *this; 
        }
        static char _buf[35];
        char *_pos = _buf + 35;
        while (x >= 10000)
            *--reinterpret_cast<u32 *&>(_pos) = m[x % 10000], x /= 10000;
        *--reinterpret_cast<u32 *&>(_pos) = m[x];
        _pos += (x < 1000) + (x < 100) + (x < 10);
        _O_pos = std::copy(_pos, _buf + 35, _O_pos);
        return *this;
    }

    IO_Tp &operator<<(char ch)
    {
        *_O_pos++ = ch;
        return *this;
    }
} IO;