D1. Построение массива (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \le 1000$$$ и $$$m=\frac{n(n+1)}{2}$$$.

Вам даны два целых числа $$$n$$$ и $$$m$$$. Нужно построить целочисленный массив $$$a$$$ длины $$$n$$$, который удовлетворяет $$$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 \color{red}{1000}$$$, $$$m\color{red}{=}\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» будут приняты как положительный ответ.

Пример
Входные данные
6
1 1
1 1 1
1 1
2 1 1
2 3
1 1 1
1 1 2
1 2 2
2 3
1 1 1
1 2 2
2 1 2
3 6
1 1 1
1 1 2
1 1 3
2 2 2
2 2 3
2 3 3
3 6
2 1 1
1 1 2
2 2 3
1 3 3
1 2 2
2 1 3
Выходные данные
YES
0
YES
-1
YES
0 0
NO
YES
1 -1 -1
NO
Примечание

В первом наборе входных данных единственное ограничение состоит в том, что $$$a_1+a_1$$$ неотрицательно, что означает, что $$$a_1$$$ неотрицательно. Следовательно, $$$a_1$$$ может быть любым неотрицательным целым числом.

Во втором наборе входных данных единственное ограничение состоит в том, что $$$a_1+a_1$$$ отрицательно, что означает, что $$$a_1$$$ отрицательно. Следовательно, $$$a_1$$$ может быть любым отрицательным целым числом.

В четвёртом наборе входных данных первое и второе ограничения означают, что и $$$a_1$$$, и $$$a_2$$$ неотрицательны. Однако третье ограничение требует, чтобы $$$a_1+a_2$$$ была отрицательной, что приводит к противоречию.