P8860 Dynamic Graph Connectivity.

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.**

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 $q$ lines, each containing an integer $0$ or $1$. If the $x$-th edge was deleted in this query, output $1$, otherwise output $0$.

#### 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 | Test Point ID | $n,m \leq$ | $q \leq$ | Special Constraints | |:-------------:|:----------:|:--------:|:-------------------:| | $1 \sim 2$ | $1000$ | $1000$ | None | | $3 \sim 6$ | $5000$ | $2 \times 10^5$ | None | | $7 \sim 8$ | $2 \times 10^5$ | $2 \times 10^5$ | It is guaranteed that among all queries, at most $1$ edge is not deleted | | $9 \sim 12$ | $2 \times 10^5$ | $2 \times 10^5$ | It is guaranteed that among all queries, at most $5$ edges are not deleted | | $13 \sim 16$ | $2 \times 10^5$ | $2 \times 10^5$ | Treating the directed graph as an undirected graph still gives the correct answer | | $17 \sim 20$ | $2 \times 10^5$ | $2 \times 10^5$ | None | 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