D. Определите победные острова в гонке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
МУУУУУУУУУУУУУУУУУ
— Корова Бесси, Искусство гонок по островам

Две коровы фермера Джона, Бесси и Элси, планируют участвовать в гонках по $$$n$$$ островам. Существует $$$n - 1$$$ основных мостов, соединяющих остров $$$i$$$ с островом $$$i + 1$$$ для всех $$$1 \leq i \leq n - 1$$$. Кроме того, существует $$$m$$$ альтернативных мостов. Элси может использовать и основные, и альтернативные мосты, а Бесси — только основные. Все мосты являются односторонними и могут использоваться только для перемещения с острова с меньшим индексом на остров с большим индексом.

Изначально Элси находится на острове $$$1$$$, а Бесси — на острове $$$s$$$. Коровы ходят по очереди, причем Бесси ходит первой. Предположим, что корова находится на острове $$$i$$$. Во время хода коровы, если есть мост, соединяющий остров $$$i$$$ с островом $$$j$$$, то корова может переместиться на остров $$$j$$$. Затем остров $$$i$$$ разрушается, и все мосты, соединяющие остров $$$i$$$, также разрушаются. Обратите внимание на следующее:

  • Если нет мостов, соединяющих остров $$$i$$$ с другим островом, то остров $$$i$$$ разрушается, и эта корова выбывает из гонки.
  • Если другая корова также находится на острове $$$i$$$, то после того, как эта корова переместится на другой остров, остров разрушится, и другая корова выбывает из гонки.
  • После того, как остров или мост разрушились, ни одна корова не может ими воспользоваться.
  • Если корова выбывает из гонки, ее ход пропускается до конца гонки.

Гонка заканчивается, как только одна из коров достигнет острова $$$n$$$. Можно показать, что независимо от стратегий коров, хотя бы одна из них достигнет острова $$$n$$$. Бесси побеждает тогда и только тогда, когда она первой достигает острова $$$n$$$.

Для каждого $$$1 \leq s \leq n - 1$$$ определите, выиграет ли Бесси, если она начнет гонку на острове $$$s$$$. Предположим, что обе коровы следуют оптимальным стратегиям, чтобы обеспечить себе победу.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$) — количество островов и количество альтернативных мостов.

Следующие $$$m$$$ строк каждого набора входных данных содержат по два числа $$$u$$$ и $$$v$$$ ($$$1 \leq u < v \leq n$$$) — острова, которые соединяет альтернативный мост. Гарантируется, что все альтернативные мосты различны и не совпадают с основными мостами.

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

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

Для каждого набора входных данных выведите в отдельной строке бинарную строку длины $$$n - 1$$$. $$$i$$$-й символ равен $$$1$$$, если Бесси может выиграть, если она начнет с острова $$$i$$$. В противном случае он равен $$$0$$$.

Пример
Входные данные
5
6 0
6 1
2 6
6 1
1 5
10 4
1 3
1 6
2 7
3 8
15 3
2 8
4 9
8 15
Выходные данные
11111
11011
10011
100001111
11000111000111
Примечание

В первом наборе входных данных нет альтернативных мостов, по которым Элси могла бы обогнать Бесси и первой достичь острова $$$n$$$, поэтому Бесси выиграет на всех островах, потому что она всегда ходит первой.

Во втором случае Бесси проиграет, если начнет с острова $$$3$$$, потому что:

  • Ход Бесси: Перейти по основному мосту с острова $$$3$$$ на остров $$$4$$$.
  • Ход Элси: Перейти по основному мосту с острова $$$1$$$ на остров $$$2$$$.
  • Ход Бесси: Перейти по основному мосту с острова $$$4$$$ на остров $$$5$$$.
  • Ход Элси: Перейти по альтернативному мосту с острова $$$2$$$ на остров $$$6$$$. Элси первой достигает острова $$$n$$$.