310691: CF1870H. Standard Graph Problem

H. Standard Graph Problemtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given a weighted directed graph with $n$ vertices and $m$ edges. Each vertex in the graph can be either highlighted or normal. Initially, all vertices are normal. The cost of the graph is defined as the minimum sum of edge weights that need to be selected so that from each normal vertex one can reach at least one highlighted vertex using the selected edges only. If it is not possible to select the edges, the cost is $-1$ instead.

Your task is to compute the cost of the graph after each of the $q$ queries. The queries can be of two types:

• $+\;v_i$ makes vertex $v_i$ highlighted; it is guaranteed that the vertex is normal before the query.
• $-\;v_i$ makes vertex $v_i$ normal; it is guaranteed that the vertex is highlighted before the query.

Output the cost of the graph after each of the $q$ queries.

Input

The first line contains three integers $n$, $m$, and $q$ ($3 \le n \le 2 \cdot 10^5, 1 \le m, q \le 2 \cdot 10^5$) — the number of vertices in the graph, the number of edges, and the number of queries.

The next $m$ lines contain the edges of the graph, one edge per line. The $i$-th line contains three integers $u_i$, $v_i$, and $c_i$ ($1 \leq u_i, v_i \leq n, u_i \ne v_i, 1 \leq c_i \leq 10^6$) — the endpoints of the $i$-th edge (from $u_i$ to $v_i$) and its weight ($c_i$).

The next $q$ lines contain the queries, one query per line. The $i$-th line contains $+\;v_i$, if it is a query of the first type, and $-\;v_i$, if it is a query of the second type ($1 \leq v_i \leq n$).

Output

Output $q$ numbers. The $i$-th number is the cost of the graph after the first $i$ queries.

ExamplesInput

4 5 6
1 2 1
2 3 5
3 2 3
4 1 8
2 1 4
+ 1
- 1
+ 3
+ 1
+ 4
+ 2

Output

15
-1
14
12
4
0

Input

10 14 10
8 6 4
2 5 1
3 5 4
1 6 3
1 3 7
7 2 1
6 1 3
4 10 1
4 6 5
5 4 1
5 8 10
10 9 1
9 5 1
9 7 6
+ 7
+ 8
- 7
+ 10
+ 2
- 10
+ 5
- 2
- 5
+ 3

Output

28
24
29
19
18
24
18
19
29
20

Note

In the first test:

• After the first query, it is most profitable to select the edges with numbers $3, 4, 5$, their total cost is $15$.
• After the second query, there are no highlighted vertices, which means that there are no suitable sets of edges, the cost of the graph is $-1$.
• After the third query, it is most profitable to select the edges with numbers $1, 2, 5$, their total cost is $14$.
• After the fourth query, it is most profitable to select the edges with numbers $4$ and $5$, their total cost is $12$.
• After the fifth query, it is most profitable to select only edge number $5$, its cost is $4$.
• After the sixth query, all vertices are highlighted and there is no need to select any edges, the cost of the graph is $0$.

题目大意：

给定一个包含n个顶点和m条边的有向加权图。图中的每个顶点可以是高亮状态或正常状态。最初，所有顶点都是正常状态。图的成本定义为需要选择的最小边权重之和，以便从每个正常顶点可以使用所选边至少到达一个高亮顶点。如果无法选择边，则成本为-1。

任务是在每个查询之后计算图的成本。查询可以是两种类型：

1. + v_i 将顶点v_i设为高亮状态；保证查询前该顶点是正常状态。
2. - v_i 将顶点v_i设为正常状态；保证查询前该顶点是高亮状态。

输出每次查询后图的成本。

输入数据格式：

第一行包含三个整数n、m和q（3 ≤ n ≤ 2 × 10^5, 1 ≤ m, q ≤ 2 × 10^5）——图中顶点的数量、边的数量和查询的数量。

接下来m行包含图的边，每行一条边。第i行包含三个整数u_i、v_i和c_i（1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ c_i ≤ 10^6）——第i条边的端点（从u_i到v_i）及其权重（c_i）。

接下来q行包含查询，每行一个查询。第i行包含+ v_i，如果是第一种类型的查询，或者- v_i，如果是第二种类型的查询（1 ≤ v_i ≤ n）。

输出数据格式：

输出q个数字。第i个数字是进行前i个查询后图的成本。题目大意： 给定一个包含n个顶点和m条边的有向加权图。图中的每个顶点可以是高亮状态或正常状态。最初，所有顶点都是正常状态。图的成本定义为需要选择的最小边权重之和，以便从每个正常顶点可以使用所选边至少到达一个高亮顶点。如果无法选择边，则成本为-1。 任务是在每个查询之后计算图的成本。查询可以是两种类型： 1. + v_i 将顶点v_i设为高亮状态；保证查询前该顶点是正常状态。 2. - v_i 将顶点v_i设为正常状态；保证查询前该顶点是高亮状态。 输出每次查询后图的成本。 输入数据格式： 第一行包含三个整数n、m和q（3 ≤ n ≤ 2 × 10^5, 1 ≤ m, q ≤ 2 × 10^5）——图中顶点的数量、边的数量和查询的数量。 接下来m行包含图的边，每行一条边。第i行包含三个整数u_i、v_i和c_i（1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ c_i ≤ 10^6）——第i条边的端点（从u_i到v_i）及其权重（c_i）。 接下来q行包含查询，每行一个查询。第i行包含+ v_i，如果是第一种类型的查询，或者- v_i，如果是第二种类型的查询（1 ≤ v_i ≤ n）。 输出数据格式： 输出q个数字。第i个数字是进行前i个查询后图的成本。