seuOJ552 - So Far Away

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：3000 ms
• 空间限制：1024 MiB
• 题目标签：夏季, 2025

题目描述

So Far Away - Martin Garrix

在公元四世纪的欧洲大陆，一共有 $n$ 座城邦，每座城邦都有一个特征值 $a$。其中，对于任意两座不同的城邦 $i$ 和 $j$ 来说，它们之间有一条无向边，边的长度为 $e(i,j)=\min(a_i,a_j)$。

在随后的一个世纪里，发生了许多事件，包含以下两种类型：

• 1 $x$ $a$：城邦 $x$ 的特征值变为了 $a$。
• 2 $u$ $v$ $k$ $u_i$ $v_i$：在假设 $k$ 对城邦之间的边被断开的情况下，城邦 $u$ 和 $v$ 之间的最短距离是多少（这些边并没有真的被断开）。

对于每种类型为 $2$ 的事件，都需要输出一行整数代表答案。

输入格式

第一行，一个整数 $t(1\le t \le 10^4)$，代表数据组数。

对于每组数据：

第一行，两个整数 $n,q(2\le n\le 10^5;1\le q\le10^5)$，分别代表城邦的数量和事件的数量。

第二行，$n$ 个整数 $a_1,a_2,\dots,a_n(1\le a_i\le 10^8)$，代表初始时每个城邦的特征值。

接下来连续的 $q$ 行，每行一个事件。先输入一个整数 $op(1\le op\le 2)$，代表事件的类型。如果 $op=1$，则接下来输入两个整数 $x,a(1\le x\le n;1\le a\le n)$，代表把城邦 $x$ 的特征值修改为 $a$。如果 $op=2$，则接下来首先输入两个整数 $u,v(1\le u,v \le n,u\neq v)$，代表当前查询最短距离的两个城邦编号。接下来一个整数 $\red{k(0\le k\le \min(9,n-2))}$，代表在这次查询中被断开的边的数量，接下来有 $k$ 对互不相同的整数对 $u_i,v_i(u_i\neq v_i)$，代表在当且查询中城邦 $u_i,v_i$ 之间的边被断开。

保证同一测试点内 $n$ 和 $q$ 的总和均不会超过 $10^5$。

输出格式

对于每种类型为 $2$ 的事件，都需要输出一行整数代表答案。

可以证明的是，在题目给定的条件下，任意两对城邦之间都是相互联通的。

样例

输入样例

3
2 4
1 1
2 1 2 0
1 1 2
1 2 3
2 1 2 0
3 5
1 2 3
2 1 2 1 1 2
2 1 2 1 1 3
2 1 2 1 2 3
1 1 6
2 1 2 1 1 2
6 10
1 1 1 1 9 2
2 1 6 4 1 2 1 3 1 4 1 6
1 1 4
1 2 10
1 3 8
2 3 2 1 2 3
1 4 100000000
2 2 6 0
1 6 9
2 2 6 1 3 1
2 3 5 3 3 5 1 3 1 5

输出样例

1
2
3
1
1
5
3
2
2
8
17