F. Красивые отрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано целое число $$$n$$$ и $$$m$$$ отрезков. Каждый отрезок имеет вид $$$[l_i, r_i]$$$ и удовлетворяет условию $$$1 \le l_i \le r_i \le n$$$. Обратите внимание, что могут быть дублирующиеся отрезки.

Пусть $$$p$$$ — это перестановка длины $$$n$$$, содержащая все целые числа $$$0,1,2,\dots,n-1$$$ ровно один раз.

Существует мультисет $$$M$$$, который изначально пуст.

Для каждого отрезка $$$[l_i, r_i]$$$:

  • рассмотрите подмассив $$$p[l_i \dots r_i]$$$,
  • вычислите $$$v_i = \operatorname{mex}$$$$$$^{\text{∗}}$$$$$$(p[l_i \dots r_i])$$$,
  • вставьте $$$v_i$$$ в $$$M$$$.

После обработки всех отрезков $$$M$$$ будет равно $$$\{v_1, v_2, \dots, v_m\}$$$.

Ваша задача — построить перестановку $$$p$$$ длины $$$n$$$, содержащую все целые числа $$$0,1,2,\dots,n-1$$$ ровно один раз, так чтобы $$$\operatorname{mex}(M)$$$ был минимизирован.

$$$^{\text{∗}}$$$$$$\operatorname{mex}(a)$$$ обозначает минимальное исключенное (MEX) целое число в $$$a$$$. Например, $$$\operatorname{mex}([2,2,1])=0$$$, потому что $$$0$$$ не принадлежит массиву, и $$$\operatorname{mex}([0,3,1,2])=4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ присутствуют в массиве, но $$$4$$$ нет.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Описание каждого набора следует далее.

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 3000$$$, $$$1 \le m \le 3000$$$).

Следующие $$$m$$$ строк содержат по два целых числа, разделенных пробелом $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$), которые задают отрезок.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$3000$$$, а сумма $$$m$$$ по всем наборам входных данных не превышает $$$3000$$$.

Выходные данные

Для каждого набора входных данных выведите перестановку $$$p$$$ длины $$$n$$$, содержащую все целые числа $$$0,1,2,\dots,n-1$$$ ровно один раз, так чтобы $$$\operatorname{mex}(M)$$$ был минимизирован.

Если есть несколько ответов, вы можете вывести любой из них.

Пример
Входные данные
5
3 1
1 2
3 5
1 1
1 2
2 2
2 2
2 3
4 5
1 2
2 3
3 4
1 1
4 4
5 4
3 5
1 1
2 4
4 4
4 2
1 3
2 4
Выходные данные
2 0 1
2 1 0 
0 2 1 3 
2 0 1 3 4 
3 1 0 2
Примечание

Для первого примера, если мы выберем построить $$$p = [2, 0, 1]$$$, тогда $$$M = \{\operatorname{mex}(2, 0)\} = \{1\}$$$. Теперь $$$\operatorname{mex}(M) = 0$$$.

Для третьего примера, если мы выберем построить $$$p = [0, 2, 1, 3]$$$, тогда $$$M = \{\operatorname{mex}(0, 2), \operatorname{mex}(2, 1), \operatorname{mex}(1, 3), \operatorname{mex}(0), \operatorname{mex}(3)\} = \{1, 0, 0, 1, 0\}$$$. Теперь $$$\operatorname{mex}(M) = 2$$$.

Для четвертого примера, если мы выберем построить $$$p = [2, 0, 1, 3, 4]$$$, тогда $$$M = \{\operatorname{mex}(1, 3, 5), \operatorname{mex}(2), \operatorname{mex}(0, 1, 3), \operatorname{mex}(4)\} = \{0, 0, 2, 0\}$$$. Теперь $$$\operatorname{mex}(M) = 1$$$.

Для пятого примера, если мы выберем построить $$$p = [3, 1, 0, 2]$$$, тогда $$$M = \{\operatorname{mex}(3, 1, 0), \operatorname{mex}(1, 0, 2)\} = \{2, 3\}$$$. Теперь $$$\operatorname{mex}(M) = 0$$$.