AT_abc328_f [ABC328F] Good Set Query

题目描述

题目内容

给定 $Q$ 个三元组 $(a_1,b_1,d_1),(a_2,b_2,d_2),...,(a_Q,b_Q,d_Q)$ 。

集合 ${1,2,...,Q}$ 的一个子集 $S$ 被定义为好的子集，当且仅当存在一个长度为 $N$ 的序列 $(X_1,X_2,...,X_N)$ 满足以下条件：

对于所有 $i\in S$ ， $X_{a_i}-X_{b_i}=d_i$ 。

将 $S$ 初始化为空集，对于 $i=1,2,...,Q$ 依次进行以下操作：

如果 $S\cup \{i\}$ 是一个好的集合，那么将 $S$ 替换成 $S\cup \{i\}$ 。

以升序输出 $S$ 中的所有元素。

输入格式

从标准输入流读入，格式如下：

$$N\quad Q\\ a_1\quad b_1\quad d_1\\ a_2\quad b_2\quad d_2\\ .\\ .\\ .\\ a_Q\quad b_Q\quad d_Q\\$$

输出格式

以升序按照以下格式输出集合 $S$ 中的所有元素 $(s_1,s_2,...,s_k)$ ：

$$s_1\quad s_2\quad ...\quad s_k$$

输入输出样例 #1

输入 #1

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

输出 #1

1 2 4 5

输入输出样例 #2

输入 #2

200000 1
1 1 1

输出 #2

输入输出样例 #3

输入 #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

说明/提示

• 所有输入元素为整数。
• $1\le N,Q\le 2\times 10^5$
• $1\le a_i,b_i\le N$
• $-10^9\le d_i\le 10^9$