题目大意

有一个二分图，构造一种对边的染色方案，使得没有两个颜色相同的边共顶点。

假设对于给定二分图的答案是 $C$，记 $X$ 是大于等于 $C$ 的最小的 $2$ 的整次幂，你只需要给出一个方案，使得颜色数量不多于 $X$.。

思路概述

设度数最大的点的度数为 $D$，那么显然的，如果答案 $C>D$，也就是说我们只要构造出一种颜色数量不超过 $2^{\left \lfloor log_2D \right \rfloor}$ 的方案数。假设我们有一个边集 $e$，如果每个点的度数都 $\leq 1$，那么显然此时答案为 $1$，否则我们可以考虑把这个边集划分为两个边集 $e_1,e_2$ 使得每一个点的度数都尽量平分。重复这样的操作就可以。其他的细节就是可以用欧拉回路割边。时间复杂度 $O(m \log n)$。

代码部分

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+5;
const int M=5e5+5;
int L,R,m,U[M],V[M],du[N],st[N];
int fa[M],val[M],tag[M],res[M];
vector<int>v;
int find(int x)
{
	if(fa[x]==x)
		return x;
	int tmp=fa[x];
	fa[x]=find(fa[x]);
	val[x]^=val[tmp];
	return fa[x];
}
void upd(int x)
{
	find(x);
	if(!(val[x]^tag[fa[x]]))
	{
		tag[fa[x]]^=1;
	}
}
void unionset(int x,int y)
{
	int u=find(x),v=find(y);
	if(u!=v)
	{
		val[u]=val[x]^val[y]^1;
		fa[u]=v;
	}
}
void solve(vector<int>&v,int cur)
{
	if(v.size()==0)
		return;
	for(auto e:v)
	{
		fa[e]=e;
		val[e]=0;
		tag[e]=0;
		st[U[e]]=st[V[e]]=0;
	}
	int f=0;
	for(auto e:v)
	{
		int x=U[e],y=V[e];
		if(st[x]||st[y])f=1;
		if(!st[x]&&!st[y])
		{
			st[x]=st[y]=e;
		}
		else if(!st[x])
		{
			upd(st[y]);
			unionset(e,st[y]);
			st[x]=e;
			st[y]=0;
		}
		else if(!st[y])
		{
			upd(st[x]);
			unionset(e,st[x]);
			st[y]=e;
			st[x]=0;
		}
		else
		{
			upd(st[x]);
			upd(st[y]);
			unionset(e,st[x]);
			unionset(e,st[y]);
			st[x]=st[y]=0;
		}
	}
	if(f==0)
	{
		for(auto e:v)
			res[e]=1;
	}
	else
	{
		vector<int>vl,vr;
		for(auto e:v)
		{
			find(e);
			if(val[e]^tag[fa[e]])
			{
				vr.push_back(e);
			}
			else
			{
				vl.push_back(e);
			}
		}
		solve(vl,cur>>1);
		solve(vr,cur>>1);
		for(auto e:vr)
			res[e]+=cur>>1;
	}
}
int main()
{
	cin>>L>>R>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>U[i]>>V[i];
		V[i]+=L;
		du[U[i]]++;
		du[V[i]]++;
		v.push_back(i);
	}
	int dmax=0;
	for(int i=1;i<=L+R;i++)
		dmax=max(dmax,du[i]);
	int x=2;
	while(x<dmax)
		x<<=1;
	solve(v,x);
	cout<<x<<endl;
	for(int i=1;i<=m;i++)
		cout<<res[i]<<endl;
}