题目描述

对于整数序列 $p_1,\ldots,p_n$，我们称 $p_i$ 是一个前缀最大值当且仅当不存在 $1\le j<i$ 使得 $p_j\ge p_i$。

对于整数序列 $p_1,\ldots,p_n$，定义其权值为其前缀最大值个数。

小巡有一个包含 $n$ 个点和 $m$ 条无向边的连通图，点的编号为 $1 \sim n$。保证图连通，不保证图是简单图。

音理有 $q$ 个询问，每次给定两个点 $s,t$，请你找出从点 $s$ 出发、在点 $t$ 结束的路径 $p_1, \dots, p_k$（$p_1 = s$，$p_k = t$，且存在连接点 $p_i, p_{i + 1}$ 的边），使得序列 $p_1, \ldots, p_k$ 的权值最小。你只需要求出最小权值。

特别地，我们不要求你找到的路径是简单路径。也就是说，可以经过重复的边或者点。

输入格式

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

接下来 $m$ 行，每行两个正整数 $u,v$，表示一条连接点 $u, v$ 的边。

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

输出格式

$q$ 行，每行一个正整数，表示对应询问的答案。

8 10 4
1 8
2 5
3 6
2 6
3 8
1 6
2 1
4 8
3 4
6 7
2 7
4 3
5 4
3 8

2
1
2
2

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

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

提示

【样例解释 #1】

样例的图如下：

• 对于询问 $2,7$，其中一条权值最小的路径是 $(2,1,8,3,6,7)$，权值为 $2$。
• 对于询问 $4,3$，其中一条权值最小的路径是 $(4,3)$，权值为 $1$。
• 对于询问 $5,4$，其中一条权值最小的路径是 $(5,2,6,3,4)$，权值为 $2$。
• 对于询问 $3,8$，其中一条权值最小的路径是 $(3,8)$，权值为 $2$。

【数据范围】

本题采用捆绑测试。

• 特殊性质 A：保证 $m=n-1$。
• 特殊性质 B：保证对于任意 $i\in[1,n]$ 满足 $V'=\{1,2,\ldots,i\}$ 的导出子图是连通图。

对于 $100\%$ 的数据，保证 $1\le n,m,q\leq 2\times 10^5$，$1\le u,v,s,t\le n$，保证图连通，不保证图不存在重边或自环。