配点 : 800 点
問題文
N 存在一个由顶点组成的完整 DAG。换句话说,该图中的任何一组顶点 i, j \ (1 \leq i < j \leq N) 有顶点 i 到顶点 j 有边缘,而且它们是唯一的边缘。 您将按顺序收到
M 询问,因此请回答它们。 第i 个查询如下。 删除
- 頂点 X_i 假设一直下雨,直到 Y_i 的边。然后是顶点 找到到 1 到顶点 Z_i 的最短距离。
制約
- 1 \leq N, M \leq 3 \times 10^5
- \displaystyle M \leq \frac{N(N - 1)}{2}
- 1 \leq X_i < Y_i \leq N
- 1 \leq Z_i \leq N
- (X_i, Y_i) \neq (X_j, Y_j) \ (i \neq j)
- 所有输入均为整数
配点
分数由以下子作业确定。
- (200 点) N \leq 1000
- 没有其他限制。 打印第
入力
输入是按以下格式从标准输入给出的。
N M X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_M Y_M Z_M
出力
M 行。i 行中, i 个查询的答案。然而,顶部
如果无法到达 Z_i 输出 -1 。
对于最多
入力例 1
4 6 1 2 3 3 4 4 2 4 3 1 3 4 1 4 3 2 3 4
出力例 1
1 1 1 1 -1 -1
4 的查询,顶点 1 到顶点 Z_i 仍然有优势,所以答案是 1 。对于其他查询,顶点
无法到达 Z_i ,因此
输出 -1 。
入力例 2
6 10 3 5 4 2 4 2 1 3 3 3 6 6 1 4 1 1 6 1 1 5 6 4 6 6 3 4 1 4 5 6
出力例 2
1 1 2 1 0 0 2 2 0 2