Description
Berland 和 Beerland 之间有发达的航班网络，它们都属于 Berland 国营公司 BerAvia。每条航线将 Berland 的一个城市和 Beerland 的一个城市连接起来。
最近，Berland 决定私有化 BerAvia，他们将航线卖给了 $k$ 家私人公司。这些公司希望航线的划分尽量均匀。
具体地，对每个城市 $i$，定义不均匀度
$$w_i=\max_j a_{i,j}-\min_j a_{i,j}$$
其中，$a_{i,j}$ 代表公司 $j$ 拥有的经过 $i$ 市的航线数量。
Berland 政府希望不均匀度的平均值最小，请帮助它们找到最佳方案，并输出不均匀度的和。
Idea
这道题可以跑网络流但是我不会。
我们将每个城市拆分成数目最少的点，使得每个点的度数 $\leq k$。对于新图，做二分图最小边染色即可，可以证明二分图最小边染色数 $=\max \text{Degree}$。具体地，我们利用一个类似匈牙利的算法实现。
设 $f_{i,j}$ 代表新图上从 $x$ 点出发，颜色为 $j$ 的边另一个端点的编号。每次新加入一条从 $x$ 到 $y$ 的边时，找到这两个端点可以使用的最小颜色编号，分别设为 $cx,cy$。如果 $cx=cy$，可以直接加边；否则，我们要为 $y$ 端点处占用了 $cx$ 的边更换颜色。具体地，我们可以找到一条从 $y$ 出发的，颜色为 $cx,cy$ 交替出现的增广路，将这条增广路上的 $cx,cy$ 互换。
这样做的时间复杂度为 $\Theta(\frac{m^2}{k}+mn)$。
Code
#include <bits/stdc++.h>
#define maxn 310
#define maxm 90010
using namespace std;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x;
}
int nA,nB,m,k,ans,x,y,c1,c2,cnt;
int deg[maxn<<1],be[maxm],w[maxn],w2[maxn];
int id[10005][maxn],f[10005][maxn];
void rv(int x,int c1,int c2){
swap(f[x][c1],f[x][c2]);
swap(id[x][c1],id[x][c2]);
be[id[x][c2]]=c2;
if (f[x][c2]) rv(f[x][c2],c2,c1);
}
int main(){
nA=read(),nB=read(),m=read(),k=read();
for (int i=1;i<=m;++i){
x=read(),y=read();
if (deg[x]%k==0) w[x]=++cnt;
if (deg[nA+y]%k==0) w2[y]=++cnt;
deg[x]++,deg[nA+y]++;
x=w[x],y=w2[y];
c1=0,c2=0;
for (int j=1;j<=k;++j)
if (!f[x][j]) {c1=j;break;}
for (int j=1;j<=k;++j)
if (!f[y][j]) {c2=j;break;}
if (f[y][c1]) rv(y,c1,c2);
f[x][c1]=y;id[x][c1]=i;
f[y][c1]=x;id[y][c1]=i;
be[i]=c1;
}
for (int i=1;i<=nA+nB;++i)
ans+=(bool)(deg[i]%k);
printf("%d\n",ans);
for (int i=1;i<=m;++i)
printf("%d ",be[i]);
putchar('\n');
return 0;
}