CF2245D1 Construct an Array (Easy Version)

这是该问题的简单版本。与困难版本的区别在于本题中 $n \le 1000$，并且 $m = \frac{n(n+1)}{2}$。 你将获得两个整数 $n$ 和 $m$。你需要构造一个长度为 $n$ 的整数数组 $a$，使其满足 $m$ 个限制条件。每个限制条件可以表示为一个三元组 $(o, i, j)$，其中 $o \in \{1,2\}$，$1 \le i \le j \le n$： - 如果 $o = 1$，则要求 $a_i + a_j$ 非负。 - 如果 $o = 2$，则要求 $a_i + a_j$ 为负。

每个测试用例包含多组数据。第一行为测试用例组数 $t$（$1 \le t \le 10^4$）。之后是每组测试数据的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 1000$，$m = \frac{n(n+1)}{2}$），分别表示你需要构造的数组 $a$ 的长度和限制条件的数量。 接下来的 $m$ 行中，每行包含三个整数 $o$、$i$、$j$（$o \in \{1,2\}$，$1 \le i \le j \le n$），表示一个限制条件。保证每对 $i$ 和 $j$（$1 \le i \le j \le n$）仅在至多一个限制条件中出现一次。 还保证所有测试用例的 $m$ 之和不超过 $10^6$。

对于每个测试用例，如果不存在这样的数组 $a$，则输出 “NO”。 否则，先在一行内输出 “YES”。然后输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$|a_i| \le 10^9$），表示你构造的数组 $a$。可以证明在题目限制下，如果存在符合条件的数组，则一定存在一个所有元素的绝对值均不超过 $10^9$ 的解。 如果存在多组满足要求的数组，你可以输出其中任意一组。 你可以输出任意大小写组合的单词。例如，“yEs”、“yes”、“Yes” 和 “YES” 都会被识别为肯定回答。

在第一个测试用例中，唯一的限制条件是 $a_1 + a_1$ 非负，这意味着 $a_1$ 必须非负。所以 $a_1$ 可以是任意非负整数。 在第二个测试用例中，唯一的限制条件是 $a_1 + a_1$ 为负，这意味着 $a_1$ 必须为负。所以 $a_1$ 可以是任意负整数。 在第四个测试用例中，前两个限制条件意味着 $a_1$ 和 $a_2$ 都要非负。然而第三个限制条件又要求 $a_1 + a_2$ 为负，这会导致矛盾。 由 ChatGPT 5 翻译