Problem Description

Given a directed graph with $n$ vertices and $m$ edges, initially there exists a path from $1$ to $n$.

You need to process $q$ queries. Each query gives a positive integer $x$ in $[1,m]$. If the $x$-th edge in the original graph still exists, and after deleting the $x$-th edge of the original graph from the current graph there is still a path from $1$ to $n$, then delete the $x$-th edge of the original graph.

You need to report whether the $x$-th edge was deleted in each query.

Note: once an edge is deleted in a query, it is deleted forever. That is, queries affect each other.

Input Format

The first line contains three positive integers $n,m,q$, representing the number of vertices, the number of edges, and the number of queries in the directed graph.

The next $m$ lines each contain two positive integers $u_i,v_i$, meaning the $i$-th edge goes from $u_i$ to $v_i$.

The next $q$ lines each contain one positive integer $x$, with the same meaning as in the description.

Output Format

Output $q$ lines, each containing an integer $0$ or $1$.

If the $x$-th edge was deleted in this query, output $1$, otherwise output $0$.

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

0
1
1
0
0

10 11 8
1 2
2 7
2 5
1 4
4 5
4 8
8 9
9 5
3 2
3 6
5 10
10
5
11
10
3
7
1
4

1
1
0
0
1
0
1
0

Hint

Sample Explanation

In the first sample:

Initially, the edge set of the graph is $\{ (1,2),(2,3),(3,5),(2,4),(4,5),(5,1) \}$.

If we delete the $1$-st edge $(1,2)$ of the original graph, then there is no path from $1$ to $n$, so we cannot delete the $1$-st edge.

If we delete the $2$-nd edge $(2,3)$ of the original graph, then there exists a path $1 \to 2 \to 4 \to 5$, so we can delete the $2$-nd edge, and the edge set becomes $\{ (1,2),(3,5),(2,4),(4,5),(5,1) \}$.

If we delete the $3$-rd edge $(3,5)$ of the original graph, then there exists a path $1 \to 2 \to 4 \to 5$, so we can delete the $3$-rd edge, and the edge set becomes $\{ (1,2),(2,4),(4,5),(5,1) \}$.

If we delete the $4$-th edge $(2,4)$ of the original graph, then there is no path from $1$ to $n$, so we cannot delete the $4$-th edge.

If we delete the $5$-th edge $(4,5)$ of the original graph, then there is no path from $1$ to $n$, so we cannot delete the $5$-th edge.

Constraints

For all testdata, $1 \leq n,m,q \leq 2 \times 10^5$. The given graph has no multiple edges or self-loops, and there exists a path from $1$ to $n$.

The two provided large samples satisfy the constraints of test point $1$ and test point $13$, respectively.

Translated by ChatGPT 5