P10005
P1005 距离与子图【数据加强版】
Note
欢迎同学们踊跃添加 hack 数据，本题正确的时间复杂度应为 \(O(nm)\).
理论上本题暂时未能卡掉全部不正确的做法。
也欢迎同学们测试自己通过普通版题目的代码是否正确。
普通版题目不会再进行增强数据与重测。
Description
给出一个 \(n\) 个点，\(m\) 条边的无向简单连通图，你需要回答以下两种询问。
- 给出顶点 \(u,v\)，查询 \(u,v\) 的距离（它们最短路的边数）。
- 给出顶点 \(a,b,c\)，你需要找到原图的一个边数最少的子图，满足子图中 \(a,b\) 的距离、 \(b,c\) 的距离和 \(a,c\) 的距离相较于原图不发生改变。
Format
Input
第一行输入三个正整数 \(n,m,q\)。
接下来 \(m\) 行每行输入两个正整数 \(x,y\) 表示 \(x\) 到 \(y\) 有一条边。
接下来 \(q\) 行，每行每行第一个整数 \(op\) 表示操作类型，若：
- \(op=1\)，接下来输入两个正整数 \(u,v\)，表示查询这两个顶点之间的距离。
- \(op=2\)，接下来输入三个正整数 \(a,b,c\)，表示查询上述题意中边数最小的子图边数大小。
对于全部测试点，保证 \(n\le 5000,m\le 5000,q\le 5000,1\le u,v,a,b,c\le n,op\in\{1,2\}\)，保证 \(op=2\) 的询问不超过 \(5\) 次。
保证所有操作满足题目描述，保证每一行的两个相邻整数都仅用一个空格隔开。
Output
对于每个询问，输出单独一行表示结果。
Samples
Sample Input 1
16 18 8
1 2
1 3
1 8
2 11
2 4
3 5
3 6
4 5
4 15
5 10
6 7
6 9
6 14
8 9
10 15
10 16
11 12
11 13
1 1 6
1 7 15
1 12 14
1 4 8
2 1 2 3
2 9 11 16
2 6 12 13
2 7 8 15
Sample Output 1
2
5
6
3
2
11
6
10