Edge coloring of bipartite graph

题意翻译

#### 题意 给你一个无向的二分图。现在将它的每条边染色，使得任意两条相邻（有公共顶点）的边颜色不同。请你计算一种染色方案，使得用到的颜色数量最少。 #### 输入格式 第一行包括三个整数：$a,b,m(1\leq a,b\leq1000,0\leq n\leq10^5)$，其中$a$表示左半部分的点数，$b$表示右半部分的点数，$m$表示边数。 下面$m$行，每行两个整数$x,y(1\leq x\leq a,1\leq y\leq b)$，表示左半部分中编号为$x$的点与右半部分中编号为$y$的点之间有一条无向边。输入保证没有重边。 #### 输出格式 第一行一个整数$c$，表示最少要使用多少种颜色； 第二行$m$个整数，第$i(1\leq i\leq m)$个整数$d_i(1\leq d_i\leq c)$表示第$i$条边的颜色为$d_i$。 如果解不唯一，输出任意一个即可。

题目描述

You are given an undirected bipartite graph without multiple edges. You should paint the edges of graph to minimal number of colours, so that no two adjacent edges have the same colour.

输入输出格式

输入格式

The first line contains three integers $ a,b,m $ ( $ 1<=a,b<=1000 $ , $ 0<=m<=10^{5} $ ), $ a $ is the size of the first part, $ b $ is the size of the second part, $ m $ is the number of edges in the graph. Each of the next $ m $ lines contains two integers $ x,y $ ( $ 1<=x<=a,1<=y<=b $ ), where $ x $ is the number of the vertex in the first part and $ y $ is the number of the vertex in the second part. It is guaranteed that there are no multiple edges.

输出格式

In the first line print integer $ c $ — the minimal number of colours. The second line should contain $ m $ integers from $ 1 $ to $ c $ — the colours of the edges (in the order they appear in the input). If there are several solutions, you can print any one of them.

输入输出样例

输入样例 #1

4 3 5
1 2
2 2
3 2
4 1
4 3

输出样例 #1

3
1 2 3 1 2