← 返回题目列表

AtCoder · pakencamp_2023_day2_f

F. 使其不完整

中文机器翻译题面 查看原题

配点 : 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)
  • 所有输入均为整数

配点

分数由以下子作业确定。

  1. (200 点) N \leq 1000
  2. 没有其他限制。 打印第

入力

输入是按以下格式从标准输入给出的。

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