Score : $550$ points

问题陈述

在AtCoder国家，有编号为$1$到$N$的$N$个城市，以及编号为$1$到$M$的$M$条道路。 道路$i$双向连接城市$A_i$和$B_i$，长度为$C_i$。

你需要按顺序处理$Q$个查询。查询分为以下两种类型：

• 1 i：道路$i$关闭。
• 2 x y：打印从城市$x$到城市$y$的最短距离，只使用未关闭的道路。如果从城市$x$无法到达城市$y$，则打印-1。

保证每个测试用例中第一种类型的查询最多包含$300$个。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

In the nation of AtCoder, there are $N$ cities numbered $1$ to $N$, and $M$ roads numbered $1$ to $M$.
Road $i$ connects cities $A_i$ and $B_i$ bidirectionally and has a length of $C_i$.

You are given $Q$ queries to process in order. The queries are of the following two types.

• 1 i: Road $i$ becomes closed.
• 2 x y: Print the shortest distance from city $x$ to city $y$, using only roads that are not closed. If city $y$ cannot be reached from city $x$, print -1 instead.

It is guaranteed that each test case contains at most $300$ queries of the first type.

Constraints

• $2 \leq N \leq 300$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i < B_i \leq N$
• All pairs $(A_i, B_i)$ are distinct.
• $1 \leq C_i \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• In the queries of the first type, $1 \leq i \leq M$.
• The road given in a query of the first type is not already closed at that time.
• The number of queries of the first type is at most $300$.
• In the queries of the second type, $1 \leq x < y \leq N$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $Q$

$A_1$ $B_1$ $C_1$

$\vdots$

$A_M$ $B_M$ $C_M$

$\mathrm{query}_1$

$\vdots$

$\mathrm{query}_Q$

Each query is in one of the following two formats:

1 $i$

2 $x$ $y$

Output

Process the queries in order.

Sample Input 1

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

Sample Output 1

10
11
-1

• In the first query, print the shortest distance from city $1$ to city $3$, which is $10$.
• In the second query, road $2$ becomes closed.
• In the third query, print the shortest distance from city $1$ to city $3$, which is $11$.
• In the fourth query, road $1$ becomes closed.
• In the fifth query, city $3$ cannot be reached from city $1$, so print -1.

Sample Input 2

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

Sample Output 2

-1
-1
-1