seuOJ569 - 地球上最后的夜晚

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：1000 ms
空间限制：256 MiB
题目标签：Div.1, 2025 帆软杯

题目描述

给定一张由 $n$ 个节点和 $m$ 条边构成的无向图。节点的编号是 $1,2,\cdots,n$ ，边的编号是 $1,2,\cdots,m$ 。

你需要选取若干条边。

用 01 序列 $\{a_i\}_{i=1}^m$ 来表示边的选取情况。若编号为 $i$ 的边被选，则 $a_i=1$ ；否则， $a_i=0$ 。

你的选边方案必须满足：

保留被选的边而删除不选的边后，所有节点的度数都是奇数。这有可能无法被满足，此时无解。
在满足上条要求的前提下，使序列 $a$ 的字典序最大。

对于任意两个 01 序列 $\{b_{1,i}\}_{i=1}^m$ 和 $\{b_{2,i}\}_{i=1}^m$ ，称 $b_1$ 的字典序大于 $b_2$ ，当且仅当存在整数 $i\in[1,m]$ 满足以下两个条件：对于任意整数 $j\in[1,i)$ ，都有 $b_{1,j}=b_{2,j}$ ； $b_{1,i}=1$ 而 $b_{2,i}=0$ 。容易证明，全体长度为 $m$ 的 01 序列在字典序比较下构成严格全序集。

输入格式

第一行两个整数 $n,m$ （ $2\le n\le10^6$ ， $1\le m\le10^6$ ）。

接下来 $m$ 行中的第 $i$ 行，有两个整数 $u_i,v_i$ （ $1\le u_i,v_i\le n$ ），表示编号为 $i$ 的边连接节点 $u_i$ 和 $v_i$ 。

保证图中无自环，即 $u_i\ne v_i$ 。

输出格式

若无解，输出 -1。

否则，输出一个长度为 $m$ 的 01 序列（一行 $m$ 个整数，相邻的数之间用一个空格隔开），表示你的选边方案。

样例

样例 1

输入

输出

1 0 1 0

解释

若不要求使 $a$ 的字典序最大，方案还可以是选取编号为 $2$ 和 $4$ 的边。

样例 2

输入

3 2
1 2
2 3

输出

-1