【模板】静态仙人掌
题目背景
这是一道静态仙人掌(Block Forest Data Structure)的模板题。
如果您不知道什么是仙人掌,那么此处给出无向仙人掌图的定义:
>任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。
题目描述
给你一个有 $n$ 个点和 $m$ 条边的仙人掌图,和 $q$ 组询问
每次询问两个点 $u,v$,求两点之间的最短路。
保证输入数据没有重边。
输入输出格式
输入格式
第一行三个正整数 $n,m,q$,意义如题目描述。
接下来 $m$ 行,每行三个正整数 $u,v,w$,表示 $u,v$ 之间有一条权值为 $w$ 的无向边。
然后 $q$ 行,每行两个正整数 $u,v$,询问 $u$ 到 $v$ 的最短路。
输出格式
$q$ 行,每行一个正整数,对应一次询问的结果。
输入输出样例
输入样例 #1
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7
输出样例 #1
5
6
输入样例 #2
9 10 3
1 2 1
2 3 1
2 4 4
3 4 2
4 5 1
5 6 1
6 7 2
7 8 2
8 9 4
5 9 2
1 9
5 8
3 4
输出样例 #2
7
5
2
说明
**样例1解释:**
样例1中的仙人掌是这个样子的:
![](https://cdn.luogu.com.cn/upload/pic/52854.png)
询问有两个,分别是询问 $1\rightarrow 9$ 和 $5\rightarrow 7$ 的最短路
显然答案分别为 $5$ 和 $6$。
**数据范围:**
$1\le n,q \le 10000$
$1\le m \le 20000$
$1\le w \le 10^5$
保证输入数据没有重边。
请注意时限为 $300\text{ms}$