题目

点这里看题目。

给定一张 \(n\) 个点 \(m\) 条边的无向图，保证没有重边和自环（应该）。

现在，你需要给每条边分配一个颜色。颜色只有两种。你的方案需要保证每个度数 \(\ge 2\) 的结点的邻接边的颜色不能相同。判断有无方案，如果有则数出任何一组。

所有数据满足 \(1\le n,m\le 10^5\)。

分析

首先当然需要看一下什么情况无解？画一些简单的情况：环、树......可以发现只有单独的奇环无法构造出解，其它情况都可以。

那这意味着什么呢？如果不是奇环有什么构造方法呢？如果可以想到欧拉路的话，那么这个问题就很容易了。

Remark.

关于边的染色问题常常可以见到欧拉路出现。

Note.

我原本是在考虑一个基于环的构造方法。这个方法要求我找到一个点双内“包含所有点的环”，基于这个环做一个初步的构造（交替染色）。之后如果是奇环，则需要再找一条边进行调整。

我很激动，觉得这个问题“很简单”。后来我冷静地想了想，发现这是 Hamilton 回路问题，NPC。不过想到 Hamilton 路就自然地联想到欧拉路了，于是就有了后续的思路。

我们注意到，如果连通块内存在欧拉（回）路，那么我们可以交替染色，即按欧拉路的顺序染成 01010101...。除了起点以外点都可以保证满足条件，因为进入它的边和离开它的边颜色是不同的。起点则需要额外讨论：

• 如果存在度数 \(>2\) 的点，我们可以拿这种点当起点。这样起点会在欧拉路中间再被遍历至少一次，同样满足条件。
• 否则，这个连通块必然是一个单独的环。如果是偶环则 OK，如果是奇环则 GG。

那么，存在奇度点怎么办？这个问题中的奇度点是特殊的存在，因为度数为 \(1\) 的点没有限制，而度数 \(>2\) 的点必然会被经过多于一次，这样的点必然满足条件。所以，我们可以直接将奇点配对连边。为了避免含奇点的图退化成奇环导致错判，最好保留两个奇点跑欧拉路。

所以 \(O(n+m)\) 就可以解决本题。

代码

#include <cstdio>
#include <algorithm>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int MAXN = 2e5 + 5;

template<typename _T>
inline void Read( _T &x ) {
	x = 0; char s = getchar(); bool f = false;
	while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
	if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
	if( x < 0 ) putchar( '-' ), x = -x;
	if( 9 < x ) Write( x / 10 );
	putchar( x % 10 + '0' );
}

struct Edge {
	int to, nxt;
} Graph[MAXN << 1];

int odd[MAXN], len = 0;
int tour[MAXN], tot = 0;

bool vis[MAXN];
int q[MAXN], h, t;

int deg[MAXN];
int head[MAXN], cur[MAXN], cnt = 1;
int ans[MAXN]; bool edgVis[MAXN];

int N, M;

inline void AddEdge( const int &from, const int &to ) {
	Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
	head[from] = cnt, deg[to] ++;
}

inline void BFS( const int &s ) {
	h = 1, t = 0;
	vis[q[++ t] = s] = true;
	while( h <= t ) {
		int u = q[h ++];
		for( int i = head[u], v ; i ; i = Graph[i].nxt )
			if( ! vis[v = Graph[i].to] ) vis[q[++ t] = v] = true;
	}
}

void DFS( const int &u ) {
	for( int &i = cur[u] ; i ; i = Graph[i].nxt )
		if( ! edgVis[i >> 1] ) {
			int id = i >> 1;
			edgVis[i >> 1] = true;
			DFS( Graph[i].to );
			tour[++ tot] = id;
		}
}

int main() {
	Read( N ), Read( M );
	rep( i, 1, M ) {
		int u, v; Read( u ), Read( v );
		AddEdge( u, v ), AddEdge( v, u );
	}
	rep( i, 1, N ) if( ! vis[i] ) {
		BFS( i ), len = 0;
		int edgCnt = 0;
		rep( j, 1, t ) {
			edgCnt += deg[q[j]];
			if( deg[q[j]] & 1 ) odd[++ len] = q[j];
		}
		edgCnt >>= 1, tot = 0;
		if( edgCnt == t && edgCnt % 2 && ! len )
			return puts( "0" ), 0;
		if( ! len ) {
			int s = q[1];
			rep( j, 2, t )
				if( deg[q[j]] > 2 ) {
					s = q[j]; break;
				}
			rep( j, 1, t ) cur[q[j]] = head[q[j]];
			DFS( s );
		} else {
			for( int j = 3 ; j + 1 <= len ; j += 2 )
				AddEdge( odd[j], odd[j + 1] ),
				AddEdge( odd[j + 1], odd[j] );
			rep( j, 1, t ) cur[q[j]] = head[q[j]];
			DFS( odd[1] );
		}
		std :: reverse( tour + 1, tour + 1 + tot );
		rep( i, 1, tot ) ans[tour[i]] = ( i - 1 ) % 2 + 1;
	}
	rep( i, 1, M ) Write( ans[i] ), putchar( '\n' );
	return 0;
}