请注意本题可能数据过水。

以下的题解中，都假设图是连通图。如果不是，可以对各连通块分别求解。

我们看到这种“判断是否有解，有解输出一组”的题，我们应该想到：思考一种最简单无解情况，并且试图构造方案使其他情况下都有解；如果构造不出来，排除无解情况后，在更小的范围内继续构造。

很幸运本题只有一种最简单的无解情况，那就是整张图就是一个大环，环上只有奇数条边，并且除了这个大环以外没有其他边。也即：整张图有奇数条边，且每个点的度数都为 $2$ 的情况。容易证明这种情况下是无解的，我们接下来要构造方案使其他情况下都有解。

首先把欧拉路转为欧拉回路。具体的，如果某个点 $u$ 的度数 $d_u$ 满足 $2\nmid d_u$，那么在 $u$ 和虚拟点 $0$ 之间连一条边。

接下来就可以跑欧拉回路了。从一个满足 $d_u\ge 3$ 的点开始，对欧拉回路上的每一条边交替染色，绕一圈染回来，如果 $u$ 所连的所有回路边都染的相同颜色，则对 $u$ 分叉出去的边染一种不同颜色，然后接着交替往下染。

注意，为什么不能从一个 $d_u=2$ 的点开始染？因为如果这样，有可能欧拉回路的长度是奇数，那么 $u$ 所连接的所有回路边都会是相同颜色，但是又因为 $u$ 没有其他边可连，这样就出错了。

这样就能在 $O(n+m)$ 的时间复杂度内做掉这道题了。

#include <cstdio>
#include <algorithm>
inline void read(int &x)
{
	x = 0;
	char c = getchar();
	while (c < '0' || c > '9')
		c = getchar();
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c & 15), c = getchar();
}
const int MAXN = 1e5 + 7, MAXM = 3e5 + 7;
struct Edge
{
	int v, nxt;
} e[MAXM << 2];
int n, m, ce, idx = 1, h[MAXN], d[MAXN], p[MAXN];
bool vis[MAXN], evis[MAXM << 1], cc, col[MAXM << 1];
inline void add(int u, int v)
{
	e[++idx] = {v, h[u]}, h[u] = idx;
}
void DFS(int u)
{
	vis[u] = true;
	for (int i = h[u], v = e[i].v; i; v = e[i = h[u]].v)
		if (h[u] = e[i].nxt, !evis[i >> 1])
			evis[i >> 1] = true, ++ce, DFS(v), col[i >> 1] = (cc = !cc);
}
int main()
{
	read(n), read(m);
	for (int i = 1; i <= n; ++i)
		p[i] = i;
	for (int i = 1, u, v; i <= m; ++i)
		read(u), read(v), add(u, v), add(v, u), ++d[u], ++d[v];
	for (int i = 1; i <= n; ++i)
		if (d[i] & 1)
			add(0, i), add(i, 0);
	std::sort(p + 1, p + n + 1, [&](const int &x, const int &y) { return d[x] > d[y]; });
	ce = 0, cc = false, DFS(0);
	for (int i = 1; i <= n; ++i)
		if (!vis[p[i]])
		{
			ce = 0, cc = false, DFS(p[i]);
			if ((ce & 1) && d[p[i]] <= 2)
				return putchar('0'), 0;
		}
	for (int i = 1; i <= m; ++i)
		printf("%d\n", col[i] + 1);
	return 0;
}