Edge Coloring of Bipartite Graph

AC一覧

Problem Statement
問題文

Given a bipartite graph with $L + R$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$.

Calculate the proper edge coloring which gives the edge chromatic number.

頂点数が $L, R$、辺が $M$ の二部グラフが与えられる。$i$ 番目の辺は $(a_i, b_i)$ である。 辺彩色数を与える辺彩色を構築せよ。

Constraints
制約

Input
入力

$L$ $R$ $M$
$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{M - 1}$ $b_{M - 1}$

Output
出力

$K$
$c_0$ 
$c_1$
$\vdots$
$c_{M - 1}$

$K$ is the edge chromatic number, and $c_i$ is the integer which repersents the color of the i-th edge. $c_i$ should satisfy $0 \leq c_i < K$.

$K$ は辺彩色数、$c_i$ は $i$ 番目の辺の色を表す整数。 $c_i$ は $0 \leq c_i < K$ を満たすとする。

Sample
サンプル

# 1

4 4 7
1 1
2 2
0 0
3 1
1 2
2 0
3 2
3
0
2
1
2
1
0
0

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions