来源：牛客网：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
Special Judge, 64bit IO Format: %lld

@[toc]

题目描述

给一个没有重边的二分图, 要求给边染色. 有公共点的边不能同色. 问最少用多少种颜色, 并任意构造一组方案. 输入描述:
第一行两个数n和m表示图的点数和边数(0<n<1001,0<m<2001). 之后m行每行2个数表示一条边的两个端点. 点从1编号到n.
保证给的是二分图.

输出描述:

第一行一个数k表示需要多少种颜色. 接下来m行每行一个数表示输入的边的颜色. 按照输入的顺序输出, 颜色从1编号到k.

示例1
输入

4 4
1 2
1 3
2 4
3 4

输出

2
1
2
2
1

题解：

题目要求有公共点的边不能同色，最后要求最少的颜色数
所以有公共点的边我们就让他同***r>二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。（也就是匹配出没有共同点的边）
边数最大的子图就是最大匹配
所以我们可以多次调用二分图最大匹配（比如匈牙利算法），为每次匹配出来的边附上色，直到全部匹配
但是有的边可能在多次最大匹配中都可以被匹配上，怎么保证最优呢？
根据题意，每个点所连的边颜色各不相同，所以答案就是度数最大的那个点，所以每次匹配有限从度数大的开始匹配
具体为什么从最大度下手？可以从反证法，假设从最小度开始匹配会怎么样。也可以看看官方解释

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+9;
int d[maxn];//点i的度数 
int x[maxn],y[maxn];
int id[maxn],col[1040][1040];
vector<int>g[maxn];
bool vis[maxn];
int match[maxn];
int n,m;

bool cmp(int x,int y)
{
    return d[x]>d[y];
}
bool dfs(int u)
{
    for(auto v:g[u])
    {
        if(!vis[v])
        {
            vis[v]=1;
            if(match[v]==0||dfs(match[v]))
            {
                match[v]=u;
                match[u]=v;
                return 1;
            }
        }
    }
    return 0;
}
void init()
{

    memset(match,0,sizeof(match));
    sort(id+1,id+1+n,cmp);
}
int main()
{

    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
        d[x[i]]++;
        d[y[i]]++;
        ans=max(ans,max(d[x[i]],d[y[i]]));
    }

    for(int i=1;i<=n;i++)id[i]=i;
    for(int i=1;i<=ans;i++)
    {
        for(int j=1;j<=m;j++)
        if(!col[x[j]][y[j]])//该边还未被标记 
        {
            g[x[j]].push_back(y[j]);//存边 
            g[y[j]].push_back(x[j]);
        }
        init();
            for(int j=1,k=id[j];j<=n;j++,k=id[j])//从度数最大的开始下手 
        {
            if(!match[k]) 
            {
                memset(vis,0,sizeof(vis));
                dfs(k);
            }
        }

        for(int j=1;j<=n;j++)//对每一次最大匹配进行染色 
        {
            if(match[j])//如果j已经匹配 
            {
                col[j][match[j]]=i;//染上色 
                d[j]--;
            }
            g[j].clear();
        }

    }
    cout<<ans<<endl;
    for(int i=1;i<=m;i++)
    cout<<col[x[i]][y[i]]<<endl;
    return 0; 
}