【模板】静态仙人掌

题目背景

这是一道静态仙人掌(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}$