Олимпиадный тренинг

Задача . G. Сколько путей?

Задача

Темы: графы Деревья дп поиск в глубину и подобное *2100

Задан ориентированный граф $G$, в котором допустимы петли (то есть рёбра из вершины в себя). В $G$ отсутствуют кратные рёбра, то есть для каждой упорядоченной пары вершин $(u, v)$ существует не более одного ребра из $u$ в $v$. Вершины пронумерованы от $1$ до $n$.

Назовём путем из $u$ в $v$ такую последовательность рёбер, что:

вершина $u$ является началом первого ребра пути;
вершина $v$ является концом последнего ребра пути;
для любой пары соседних рёбер следующее ребро начинается с вершины, на которую заканчивается предыдущее ребро.

Дополнительно будем считать, что пустая последовательность рёбер — это путь из $u$ в $u$.

Для каждой вершины $v$ выведите одно из четырёх значений:

$0$, если не существует пути из $1$ в $v$;
$1$, если существует ровно один путь из $1$ в $v$;
$2$, если существует более одного пути из $1$ в $v$ и это число является конечной величиной;
$-1$, если существует бесконечно много путей из $1$ в $v$.

Рассмотрим пример, изображённый на рисунке.

$\text{[math]}$

Тогда:

ответ для вершины $1$ равен $1$: существует ровно один путь из $1$ в $1$ (путь длины $0$);
ответ для вершины $2$ равен $0$: не существует пути из $1$ в $2$;
ответ для вершины $3$ равен $1$: существует ровно один путь из $1$ в $3$ (это ребро $(1, 3)$);
ответ для вершины $4$ равен $2$: существует более одного, но конечное число путей из $1$ в $4$ (два пути: $[(1, 3), (3, 4)]$ и $[(1, 4)]$);
ответ для вершины $5$ равен $-1$: существует бесконечно много путей из $1$ в $5$ (петля может быть использована в пути сколько угодно раз);
ответ для вершины $6$ равен $-1$: существует бесконечно много путей из $1$ в $6$ (петля может быть использована в пути сколько угодно раз).

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

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

В первой строке набора входных данных записаны два целых числа $n$ и $m$ ($1 \le n \le 4 \cdot 10^5, 0 \le m \le 4 \cdot 10^5$) — количество вершин и рёбер в графе, соответственно. Далее входные данные содержат $m$ строк с описаниями рёбер. Каждая строка состоит из двух целых чисел $a_i$, $b_i$ ($1 \le a_i, b_i \le n$) — начало и конец $i$-го ребра. Вершины графа пронумерованы от $1$ до $n$. Заданный граф может содержать петли (допустимо $a_i = b_i$), но не может содержать кратных рёбер (недопустимо $a_i = a_j$ и $b_i = b_j$ для $i \ne j$).

Сумма значений $n$ по всем наборам входных данных в тесте не превосходит $4 \cdot 10^5$. Аналогично, сумма значений $m$ по всем наборам входных данных в тесте не превосходит $4 \cdot 10^5$.

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

Выведите $t$ строк. $i$-я строка должна содержать ответ на $i$-й набор входных данных — последовательность $n$ целых чисел от $-1$ до $2$.

Примеры

№	Входные данные	Выходные данные
1	5 6 7 1 4 1 3 3 4 4 5 2 1 5 5 5 6 1 0 3 3 1 2 2 3 3 1 5 0 4 4 1 2 2 3 1 4 4 3	1 0 1 2 -1 -1 1 -1 -1 -1 1 0 0 0 0 1 1 2 1

time 4000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет