P10301 [THUWC 2020] Yazid's Chess

Given a directed graph with $n$ vertices and $m$ edges, the vertices are numbered from $1$ to $n$, and the edges are numbered from $1$ to $m$. The owner of this graph, Yazid, will perform $Q$ operations in order. Each operation is as follows: place a chess piece on a vertex $x$ and set an integer $s$. Meanwhile, the piece keeps moving along the outgoing edge with the **smallest index**. When the $i$-th edge has been traversed $w_i$ times, it will be deleted from the graph immediately. The piece keeps moving until **there is no outgoing edge to take** or **the piece has moved $s$ steps**. The vertex where the piece finally stops is called the **destination** of this operation. After that, Yazid removes the piece from the game. You need to predict the destination vertex index for each operation. Note that all operations have aftereffects. That is, the **deleted edges** and the **traversal counts** that happened in the first $Q-1$ operations **will not** be reset in the $Q$-th operation. Each operation is performed based on the state left by the previous operations.

The first line contains two integers $n,m$ separated by spaces. The next $m$ lines describe the directed graph. In this part, the $i$-th line ($1\leq i\leq m$) contains three integers $u_i,v_i,w_i$ separated by spaces, describing a directed edge from $u_i$ to $v_i$ that will be deleted after being traversed $w_i$ times. * It is guaranteed that $1\leq u_i,v_i\leq n$, and $w_i\leq 10^{18}$. The next line contains an integer $Q$. The next $Q$ lines describe the operations in order. Each line contains two integers $x,s$ separated by spaces, describing an operation. * It is guaranteed that $1\leq x\leq n$, $1\leq s\leq 10^{9}$.

Output $Q$ lines, each containing one integer, printing the destination of each operation in order. The $i$-th line should be the destination of the $i$-th operation.

**[Sample Explanation #1]** In the first operation, the piece moves as follows: 1. Place a piece on vertex $7$. 2. The outgoing edge of vertex $7$ with the smallest index is edge $7$, so the piece moves to vertex $5$ through this edge. 3. The outgoing edge of vertex $5$ with the smallest index is edge $5$, so the piece moves to vertex $2$ through this edge. 4. The outgoing edge of vertex $2$ with the smallest index is edge $3$, so the piece moves to vertex $3$ through this edge. 5. The outgoing edge of vertex $3$ with the smallest index is edge $1$, so the piece moves to vertex $1$ through this edge. 6. The outgoing edge of vertex $1$ with the smallest index is edge $2$, so the piece moves to vertex $2$ through this edge. 7. The outgoing edge of vertex $2$ with the smallest index is edge $3$, so the piece moves to vertex $3$ through this edge. At this time, edge $3$ has been traversed $2$ times and is deleted from the graph. 8. The outgoing edge of vertex $3$ with the smallest index is edge $1$, so the piece moves to vertex $1$ through this edge. 9. The piece stops at vertex $1$, so the destination of this operation is vertex $1$. In the second operation, the piece moves as follows: 1. Place a piece on vertex $6$. 2. The outgoing edge of vertex $6$ with the smallest index is edge $4$, so the piece moves to vertex $3$ through this edge. At this time, edge $4$ has been traversed $1$ time and is deleted from the graph. 3. The outgoing edge of vertex $3$ with the smallest index is edge $1$, so the piece moves to vertex $1$ through this edge. At this time, edge $1$ has been traversed $1$ time and is deleted from the graph. 4. The piece has already moved $7$ steps, so it stops at vertex $1$. Vertex $1$ is the destination of this operation. In the third operation, the piece moves as follows: 1. Place a piece on vertex $6$. 2. Vertex $6$ has no outgoing edges, so the piece can only stop at vertex $6$. Therefore, the destination of this operation is vertex $6$. **[Subtasks]** This problem has multiple subtasks. Each subtask may contain multiple test points. You can get the score of a subtask only if you pass all test points in that subtask. The test points of each subtask satisfy some special constraints, as shown in the table below. |Subtask ID|$n \le$|$m \le$|$Q \le$|$s \le$|$w \le$|Property|Score| |----|----|----|----|----|----|----|----| |1|$10^5$|$1.5 \times 10^5$|$5000$|$5000$|$10^{18}$|$0$|8| |2|$10^5$|$1.5 \times 10^5$|$5000$|$10^9$|$5000$|$0$|8| |3|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$1$|8| |4|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$2$|$12$| |5|$10^5$|$n - 1$|$10^5$|$10^9$|$10^{18}$|$3$|13| |6|$10^5$|$n$|$10^5$|$10^9$|$10^{18}$|$4$|15| |7|$10^5$|$n + 50$|$10^5$|$10^9$|$10^{18}$|$5$|8| |8|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$0$|28| For all test points, it is guaranteed that $1 \leq n\leq 10^5$, $1 \leq m\leq 1.5\times 10^5$, $1 \leq Q \leq 10^5$, $1 \leq s \leq 10^9$, $1 \leq w_i \leq 10^{18}$. - Property 0: no special property. - Property 1: the graph is generated randomly, and each edge $(u, v)$ appears with probability $1 / n^2$. - Property 2: it is guaranteed that $w_i = 10^{18}$. - Property 3: it is guaranteed that the graph forms a rooted tree. - Property 4: it is guaranteed that the graph forms a “cycle-with-trees” (huan tao shu). - Property 5: it is guaranteed that the first $n$ edges form a “cycle-with-trees” (huan tao shu). Translated by ChatGPT 5