道路封锁

题目描述

在 AtCoder 国中,有 $N$ 个城市,编号为 $1$ 到 $N$,有 $M$ 条道路,编号为 $1$ 到 $M$。

道路 $i$ 双向连接城市 $A_i$ 和城市 $B_i$,长度为 $C_i$。

给定 $Q$ 条需要按顺序处理的查询。查询有以下两种类型:

1 i:道路 $i$ 被封锁。

2 x y:仅使用未被封锁的道路,输出从城市 $x$ 到城市 $y$ 的最短距离。若从城市 $x$ 无法到达城市 $y$,则输出 -1。

保证每个测试用例中类型 1 的查询至多有 $300$ 条。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $Q$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

每条查询为以下两种格式之一:

1 $i$

2 $x$ $y$

输出格式

按顺序处理所有查询并输出。

样例

3 3 5
1 2 5
1 3 10
2 3 6
2 1 3
1 2
2 1 3
1 1
2 1 3

10
11
-1

第 1 条查询输出从城市 $1$ 到城市 $3$ 的最短距离,为 $10$。

第 2 条查询使道路 $2$ 被封锁。

第 3 条查询输出从城市 $1$ 到城市 $3$ 的最短距离,为 $11$。

第 4 条查询使道路 $1$ 被封锁。

第 5 条查询中,从城市 $1$ 无法到达城市 $3$,因此输出 -1。

4 6 6
2 3 1
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1
1 4
1 5
1 6
2 1 2
2 1 3
2 1 4

-1
-1
-1

数据范围

• $2 \le N \le 300$
• $0 \le M \le \frac{N(N-1)}{2}$
• $1 \le A_i \lt B_i \le N$
• 所有 $(A_i, B_i)$ 两两不同。
• $1 \le C_i \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• 在类型 1 的查询中,$1 \le i \le M$。
• 类型 1 的查询所给出的道路在当时尚未被封锁。
• 类型 1 的查询数量至多为 $300$。
• 在类型 2 的查询中,$1 \le x \lt y \le N$。
• 所有输入值均为整数。