D. D/D/D
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Конечно, задача D проспонсирована Декланом Акабой.

Вам дан простой связный неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. Граф не содержит петель и кратных рёбер. Вам также дано мультимножество $$$A$$$, состоящее из $$$\ell$$$ элементов. $$$$$$ A = \{A_1, A_2, \ldots, A_\ell\} $$$$$$

Начав с вершины $$$1$$$, вы можете выполнять следующий ход любое количество раз, пока мультимножество $$$A$$$ не пусто:

  • Выберите элемент $$$k \in A$$$ и удалите его из мультимножества. Вы должны удалить ровно одно вхождение $$$k$$$ в $$$A$$$.
  • Пройдите любой маршрут$$$^{\text{∗}}$$$ ровно из $$$k$$$ рёбер, чтобы достичь какой-либо вершины (возможно, той же, с которой вы начали).

Для каждого $$$i$$$ ($$$1 \le i \le n$$$) определите, существует ли последовательность ходов, которая начинается с вершины $$$1$$$ и заканчивается в вершине $$$i$$$, используя исходное мультимножество $$$A$$$.

Обратите внимание, что проверка для каждой вершины $$$i$$$ независима — вы начинаете заново с вершины $$$1$$$ и используете исходное мультимножество $$$A$$$ для каждого случая.

$$$^{\text{∗}}$$$Маршрут длины $$$k$$$ — это последовательность вершин $$$v_0, v_1, \ldots, v_{k - 1}, v_k$$$, такая что каждая пара последовательных вершин $$$(v_i, v_{i + 1})$$$ соединена ребром в графе. Последовательность может включать повторяющиеся вершины.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$\ell$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$n-1 \leq m \leq 4 \cdot 10^5$$$, $$$1 \leq \ell \leq 2 \cdot 10^5$$$) — количество вершин, количество рёбер и размер мультимножества соответственно.

Вторая строка каждого набора входных данных содержит $$$\ell$$$ целых чисел $$$A_1, A_2, \ldots, A_{\ell}$$$ ($$$1 \leq A_i \leq 10^4$$$) — элементы мультимножества.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u \lt v \le n$$$) — концы ребра в графе.

Гарантируется, что рёбра образуют простой связный граф без петель и кратных рёбер.

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

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

Для каждого набора входных данных выведите бинарную строку длины $$$n$$$, где $$$i$$$-й символ равен $$$\mathtt{1}$$$, если существует последовательность ходов, заканчивающаяся в вершине $$$i$$$, и $$$\mathtt{0}$$$ в противном случае.

Пример
Входные данные
3
6 5 2
2 3
1 2
2 3
3 4
4 5
5 6
5 5 1
5
1 2
2 3
3 4
4 5
3 5
5 4 3
100 200 300
1 2
1 3
1 4
2 5
Выходные данные
111101
11111
10001
Примечание

В первом наборе входных данных:

  • Вершина $$$1$$$ достижима без выполнения каких-либо ходов.
  • Вершина $$$2$$$ достижима, выбрав элемент $$$3 \in A$$$; один из возможных маршрутов: [$$$1 \rightarrow 2 \rightarrow 1 \rightarrow 2$$$].
  • Вершина $$$3$$$ может быть достигнута, выбрав элемент $$$2 \in A$$$ и пройдя маршрут [$$$1 \rightarrow 2 \rightarrow 3$$$].
  • Вершина $$$4$$$ достижима, выбрав элемент $$$3 \in A$$$ и следуя маршруту [$$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$$$].
  • Вершина $$$5$$$ недостижима ни одной допустимой последовательностью ходов.
  • Вершина $$$6$$$ достижима, сначала выбрав элемент $$$2 \in A$$$ и пройдя маршрут [$$$1 \rightarrow 2 \rightarrow 3$$$], затем выбрав элемент $$$3 \in A$$$ и пройдя маршрут [$$$3 \rightarrow 4 \rightarrow 5 \rightarrow 6$$$].