← 返回题目列表

AtCoder · abc328_f

I. 好的设置查询

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

分数: 525 点

问题陈述

你被给予 Q 整数三元组 套装的 (a_1, b_1, d_1), (a_2, b_2, d_2), \ldots, (a_Q, b_Q, d_Q).

一个子集 S 集合中的 \lbrace 1, 2, \ldots, Q\rbrace 被定义为 好套装 如果存在整数序列 (X_1, X_2, \ldots, X_N) 长度 N 满足:

X_{a_i} - X_{b_i} = d_i 对于所有人 i \in S.

开始于 S 作为空集,执行以下操作 i = 1, 2, \ldots, Q 按此顺序:

If S \cup \lbrace i \rbrace 是一套好的,然后更换 S 与 S \cup \lbrace i \rbrace.

打印最终集合的所有元素 S in 升序.

约束

  • 所有输入值均为整数。
  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq a_i, b_i \leq N
  • -10^9 \leq d_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N Q
a_1 b_1 d_1
a_2 b_2 d_2
\vdots
a_Q b_Q d_Q

输出

打印序列 最终组的所有元素的 (s_1, s_2, \ldots, s_k) 最终集合的所有元素 S in 升序,以空格分隔,格式如下:

s_1 s_2 \ldots s_k

示例输入 1

3 5
1 2 2
3 2 -3
2 1 -1
3 3 0
1 3 5

示例输出 1

1 2 4 5

开始于 S 作为空集,执行问题陈述中描述的操作 i = 1, 2, 3, 4, 5 按此顺序,如下。

  • 对于 i = 1,集合 S \cup \lbrace i \rbrace = \lbrace 1 \rbrace 是一个很好的集合,因为 (X_1, X_2, X_3) = (3, 1, 4) 满足问题陈述中的条件,例如,因此替换 S 与 \lbrace 1\rbrace.
  • 对于 i = 2,集合 S \cup \lbrace i \rbrace = \lbrace 1, 2 \rbrace 是一个很好的集合,因为 (X_1, X_2, X_3) = (3, 1, -2) 满足问题陈述中的条件,例如,因此替换 S 与 \lbrace 1, 2\rbrace.
  • 对于 i = 3,集合 S \cup \lbrace i \rbrace = \lbrace 1, 2, 3 \rbrace 不是一个好的设置。
  • 对于 i = 4,集合 S \cup \lbrace i \rbrace = \lbrace 1, 2, 4 \rbrace 是一个很好的集合,因为 (X_1, X_2, X_3) = (3, 1, -2) 满足问题陈述中的条件,例如,因此替换 S 与 \lbrace 1, 2, 4\rbrace.
  • 对于 i = 5,集合 S \cup \lbrace i \rbrace = \lbrace 1, 2, 4, 5 \rbrace 是一个很好的集合,因为 (X_1, X_2, X_3) = (3, 1, -2) 满足问题陈述中的条件,例如,因此替换 S 与 \lbrace 1, 2, 4, 5\rbrace.

因此,最后一组 S is \lbrace 1, 2, 4, 5\rbrace.


示例输入 2

200000 1
1 1 1

示例输出 2


决赛 S 为空。


示例输入 3

5 20
4 2 125421359
2 5 -191096267
3 4 -42422908
3 5 -180492387
3 3 174861038
2 3 -82998451
3 4 -134761089
3 1 -57159320
5 2 191096267
2 4 -120557647
4 2 125421359
2 3 142216401
4 5 -96172984
3 5 -108097816
1 5 -50938496
1 2 140157771
5 4 65674908
4 3 35196193
4 4 0
3 4 188711840

示例输出 3

1 2 3 6 8 9 11 14 15 16 17 19