Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

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

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \le 2 \cdot 10^5$$$ и $$$0 \le m \le \min(10^6,\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}{2 \cdot 10^5}$$$, $$$0 \le m \color{red}{\le} \min(10^6, \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$$$, встречается не более чем в одном ограничении.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Гарантируется, что сумма значений $$$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» будут приняты как положительный ответ.

Пример
Входные данные
10
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
2 1
2 1 2
3 4
1 1 2
1 2 3
2 1 3
2 2 2
4 0
7 7
1 1 2
2 2 3
1 3 4
2 4 5
1 5 6
2 6 7
1 7 7
Выходные данные
YES
0
YES
-1
YES
0 0
NO
YES
1 -1 -1
NO
YES
-1 -1
NO
YES
0 0 0 0
YES
6 -6 4 -4 2 -2 0
Примечание

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

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

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

В девятом наборе входных данных ограничений нет. Подходит любой целочисленный массив $$$a$$$.

В десятом наборе входных данных $$$[6,-6,4,-4,2,-2,0]$$$ является корректным решением. Заметьте, что $$$[7,-6,5,-4, 3, -2,1]$$$ также является корректным решением.