AT_abc375_f [ABC375F] Road Blocked

AtCoder 国有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$。 第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$，是双向的，长度为 $C_i$。 现在有 $Q$ 个查询，请依次处理。每个查询有以下两种类型之一： - `1 i`：第 $i$ 条道路被封闭，无法通行。 - `2 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$

请依次输出每个查询的结果。

### 数据范围 - $2 \leq N \leq 300$ - $0 \leq M \leq \frac{N(N-1)}{2}$ - $1 \leq A_i < B_i \leq N$ - $(A_i, B_i)$ 互不相同 - $1 \leq C_i \leq 10^9$ - $1 \leq Q \leq 2 \times 10^5$ - 对于第 $1$ 种类型的查询，$1 \leq i \leq M$ - 对于第 $1$ 种类型的查询，所给道路在该时刻尚未被封闭 - 第 $1$ 种类型的查询最多 $300$ 次 - 对于第 $2$ 种类型的查询，$1 \leq x < y \leq N$ - 输入均为整数 ### 样例说明 1 - 第 $1$ 个查询，输出从城市 $1$ 到城市 $3$ 的最短距离 $10$。 - 第 $2$ 个查询，将第 $2$ 条道路封闭。 - 第 $3$ 个查询，输出从城市 $1$ 到城市 $3$ 的最短距离 $11$。 - 第 $4$ 个查询，将第 $1$ 条道路封闭。 - 第 $5$ 个查询，无法从城市 $1$ 到城市 $3$，输出 $-1$。 由 ChatGPT 4.1 翻译