P10301 [THUWC 2020] Yazid 的棋

给定一张包含 $n$ 个点、$m$ 条边的有向图，点标号从 $1$ 至 $n$，边标号从 $1$ 至 $m$。 这张图的主人 Yazid 将先后执行 $Q$ 次操作，每个操作的形式为：在一个节点 $x$ 放置一个棋子，并设定一个整数 $s$，同时该棋子不停地沿着**编号最小**的出边移动，其中当第 $i$ 条边被经过 $w_i$ 次后就会立刻从图中被删除。棋子会不停移动直到**无出边可走**或**棋子已移动了 $s$ 步**。对于最终棋子停留的节点，我们把它叫做这次操作的**终点**。做完这些后，Yazid 会将该棋子移出游戏。 你需要预测 Yazid 每次操作的终点编号。 需要注意的是，所有操作都是有后效性的。也就是说，在前 $Q-1$ 步操作时**消失的边**、**经过的次数**都**不会**在第 $Q$ 次操作时被重置，即下一步操作在上一步操作基础上进行。

第一行两个用空格隔开的整数 $n,m$。 接下来 $m$ 行描述有向图。这部分中第 $i$ 行（$1\leq i\leq m$）包含三个用空格隔开的整数 $u_i,v_i,w_i$，描述一条 $u_i$ 到 $v_i$ 的经过 $w_i$ 次会被删除的有向边。 * 这里保证 $1\leq u_i,v_i\leq n$，$w_i\leq 10^{18}$。 接下来一行一个整数 $Q$。 接下来 $Q$ 行依次描述各操作，每行两个用空格隔开的整数 $x,s$，描述一个操作。 * 这里保证 $1\leq x\leq n$，$1\leq s\leq 10^{9}$。

输出 $Q$ 行，每行一个整数，依次输出各操作的终点。其中第 $i$ 行输出的是第 $i$ 个操作的终点。

**【样例解释 #1】** 第一次操作，棋子的移动步骤如下： 1. 在 $7$ 号节点放置一个棋子。 2. $7$ 号节点编号最小的出边是第 $7$ 条边，棋子通过该边移动到 $5$ 号节点。 3. $5$ 号节点编号最小的出边是第 $5$ 条边，棋子通过该边移动到 $2$ 号节点。 4. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。 5. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。 6. $1$ 号节点编号最小的出边是第 $2$ 条边，棋子通过该边移动到 $2$ 号节点。 7. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $3$ 条边已被经过了 $2$ 次，被从图中删去。 8. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。 9. 棋子停留在 $1$ 号节点，故 $1$ 号节点就是此次操作的终点。 第二次操作，棋子的移动步骤如下： 1. 在 $6$ 号节点放置一个棋子。 2. $6$ 号节点编号最小的出边是第 $4$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $4$ 条边已被经过了 $1$ 次，被从图中删去。 3. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。此时，第 $1$ 条边已被经过了 $1$ 次，被从图中删去。 4. 棋子已移动了 $7$ 步，故停留在 $1$ 号节点，$1$ 号节点是此次操作的终点。 第三次操作，棋子的移动步骤如下： 1. 在 $6$ 号节点放置一个棋子。 2. $6$ 号节点已没有出边，故棋子只能停留在 $6$ 号节点，故 $6$ 号节点是此次操作的终点。 **【子任务】** 本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。 每个子任务的测试点满足一些特殊的限制，具体如下表： |子任务编号|$n \le$|$m \le$|$Q \le$|$s \le$|$w \le$|性质|分值| |----|----|----|----|----|----|----|----| |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| 对于所有测试点，保证 $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}$。 - 性质 0：无特殊性质； - 性质 1：图为随机生成，每条边 $(u, v)$ 出现的概率为 $1 / n^2$； - 性质 2：保证 $w_i = 10^{18}$； - 性质 3：保证图构成了一棵有根树。 - 性质 4：保证图构成了一棵环套树。 - 性质 5：保证前 $n$ 条边构成了一棵环套树。