Ваша задача — построить массив $$$a$$$, состоящий из $$$n$$$ целых чисел, каждый элемент должен быть от $$$1$$$ до $$$k$$$.
Массив должен быть неубывающим ($$$a_i \le a_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$).
Также есть дополнительные ограничения на него. Каждое ограничение одного из трех следующих типов:
Постройте любой неубывающий массив, который удовлетворяет всем ограничениям, или скажите, что такого массива не существует.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных записаны три целых числа $$$n, m$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^4$$$; $$$0 \le m \le 2 \cdot 10^4$$$; $$$2 \le k \le 10$$$).
В $$$i$$$-й из следующих $$$m$$$ строк записано описание ограничения. Каждое ограничение одного из трех следующих типов:
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$. Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$.
Для каждого набора входных данных определит, существует ли неубывающий массив, который удовлетворяет всем ограничениям. Если такого не существует, то выведите -1. Иначе выведите валидный массив — $$$n$$$ целых чисел от $$$1$$$ до $$$k$$$.
4 4 0 4 2 2 3 3 1 2 3 1 2 2 3 3 2 1 1 1 2 2 3 2 3 2 3 2 5 5 5 3 2 5 7 2 4 5 10 3 4 5 6 3 3 4 7 2 1 5 7
1 2 3 4 1 3 -1 1 2 2 5 5
Название |
---|