{"extraResources":{"example.01.mu":"TVXzATMNCiFjMTsyIDENCjEgMg0KIWMyOzMgMw0KMSAyDQoyIDMNCjMgMQ0KIWMzOzggMTANCjEgMg0KMSA0DQoxIDcNCjUgMg0KNSA0DQo1IDcNCjUgMw0KMiA2DQoyIDgNCjYgOA0K"},"scoring":null,"notes":"","legend":"There are $n$ friends and $n$ houses in Chess City, both numbered from $1$ to $n$, where friend $i$ lives in house~$i$. The houses are connected by $m$ bidirectional roads, forming a connected network.\r\n\r\nChess City also has $n$ virtual chess clubs, numbered from $1$ to $n$. Each friend must choose exactly one club to join. These choices do not need to be distinct, so some clubs might not have any members.\r\n\r\nWhen friend $i$ hosts a chess party, it is attended by every friend who belongs to the same club as friend~$i$ and lives in a house directly connected to house $i$ by a road. The party is considered \\textit{successful} if the total number of attendees, including friend $i$, is even; in this case, they can all play chess simultaneously.\r\n\r\nChoose a club for each friend so that every friend's party is successful, or report that it is impossible.\r\n","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"For each test case, print a single integer $-1$ if it is impossible to assign a chess club to each friend so that every friend's party is successful.\r\n\r\nOtherwise, print $n$ integers $c_1, c_2, \\ldots, c_n$, where $c_i$ is the number of the chess club that friend $i$ should join ($1 \\le c_i \\le n$). If there are multiple answers, print any of them.","inputFile":"stdin","outputFile":"stdout","input":"Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \\le t \\le 10^4$). The description of the test cases follows.\r\n\r\nThe first line of each test case contains two integers $n$ and $m$, denoting the number of houses and the number of roads ($2 \\le n \\le 10^5$; $n - 1 \\le m \\le 2 \\cdot 10^5$).\r\n\r\nEach of the following $m$ lines contains two integers $u$ and $v$, describing a bidirectional road between houses $u$ and~$v$ ($1 \\le u, v \\le n$; $u \\ne v$). No two houses are connected by more than one road. It is possible to get from any house to any other one using the roads.\r\n\r\nIt is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and the sum of $m$ over all test cases does not exceed $2 \\cdot 10^5$.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"1 1\r\n-1\r\n3 3 6 6 6 2 6 2\r\n","input":"3\r\n2 1\r\n1 2\r\n3 3\r\n1 2\r\n2 3\r\n3 1\r\n8 10\r\n1 2\r\n1 4\r\n1 7\r\n5 2\r\n5 4\r\n5 7\r\n5 3\r\n2 6\r\n2 8\r\n6 8\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Games of Chess","interaction":null,"memoryLimit":1073741824,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Фёдор Ушаков\\\\\r\n         Разработка: & Фёдор Ушаков\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nРассмотрим задачу в терминах теории графов. Нам дан неориентированный связный граф, и нужно раскрасить его вершины в некоторое число цветов так, чтобы для каждой вершины $u$ число вершин $v$ того же цвета, соединённых с $u$ ребром, было нечётным.\r\n\r\nПри нечётном $n$ ответа не существует. Действительно, предположим обратное: пусть существует какая-то допустимая раскраска. Оставим в графе только те рёбра, концы которых имеют одинаковый цвет. После этой операции у каждой вершины степень нечётна, и так как вершин нечётное число, сумма степеней всех вершин нечётна. А в неориентированном графе сумма степеней всех вершин должна быть чётной, так как каждое ребро прибавляет к этой сумме $2$. Противоречие.\r\n\r\nДля чётного $n$ ответ всегда существует, и его можно найти с помощью следующего алгоритма:\r\n\r\n\\begin{enumerate}\r\n\\item Построим дерево обхода в глубину (DFS).\r\n\\item Повторяем, пока есть вершины:\r\n\\begin{itemize}\r\n\\item Возьмём самый глубокий лист $v$. Посмотрим на его родителя $u$. У $u$ есть $k$ детей, все они --- листья.\r\n\\item Если $k$ нечётно, то покрасим поддерево $u$ в один цвет и отрежем от остального дерева.\r\n\\item Если $k$ чётно, но есть хотя бы один лист, из которого есть хотя бы одно обратное ребро, ведущее наверх в некоторого предка вершины $u$, то этот лист переподвесим к ближайшей вершине, в которую из него есть ребро, а остальную часть поддерева отрежем так же, как в предыдущем пункте.\r\n\\item Если $k$ чётно, но рёбер наверх из листьев нет, то отрежем все эти листья и пометим, что их в конце надо будет покрасить так же, как вершину $u$, а саму вершину $u$ оставим в дереве.\r\n\\end{itemize}\r\n\\end{enumerate}\r\n\r\nМожно показать, что раскраска графа по данному алгоритму является корректной. При аккуратной реализации сложность этого решения составит $O(n + m)$."}