Задан ориентированный граф \(G\), в котором допустимы петли (то есть рёбра из вершины в себя). В \(G\) отсутствуют кратные рёбра, то есть для каждой упорядоченной пары вершин \((u, v)\) существует не более одного ребра из \(u\) в \(v\). Вершины пронумерованы от \(1\) до \(n\).
Назовём путем из \(u\) в \(v\) такую последовательность рёбер, что:
Дополнительно будем считать, что пустая последовательность рёбер — это путь из \(u\) в \(u\).
Для каждой вершины \(v\) выведите одно из четырёх значений:
Рассмотрим пример, изображённый на рисунке.
Тогда:
В первой строке записано целое число \(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\).
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
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач