問題文

部集合$V_1,V_2$の頂点数がそれぞれ $L,R$、辺数が $M$ の二部グラフが与えられる。 $i$ 番目の辺は $V_1$ の頂点 $a_i$ と $V_2$ の頂点 $b_i$ を繋いでいる。
各頂点に対する接続辺の色の集合が互いに等しい辺着色のうち、使われた色数が最大のものを構成せよ (★) 。

★を厳密な表現に言い換えよう。グラフ$G=(V,E)$の辺着色とは全射な写像 $c:E\to S$ である。このうち、 任意の頂点 $u,v$ について $\{c(e)\mid e\in E(u)\}=\{c(e)\mid e\in E(v)\}$ が成り立つ辺着色 $c$ を考える（$E(v)$ は頂点 $v$ の接続辺の集合）。 $|S|$ が最大となる $c$ を構成せよ（この着色を玉虫色着色と呼ぶことにする）。

入力

$L$ $R$ $M$
$a_1$ $b_1$
$⋮$
$a_M$ $b_M$

孤立点は存在しない。
$1\le L,R\le 1000$
$1\le M\le 10000$
$0\le a_i<L$
$0\le b_i<R$

ACに無関係なプロ向けのテストケース(evilケース)
$1\le L,R\le 100000$
$1\le M\le 100000$

出力

$K$
$c_1$
$⋮$
$c_M$

$K$ は色数、$c_i$ は $i$ 番目の辺の色を表す整数。$c_i$ は $0\le c_i<K$ を満たすとする。条件を満たす着色が複数存在する場合、いずれを出力しても良い。

サンプル

1 1 1
0 0

1
0

1 3 3
0 0
0 1
0 2

1
0
0
0

2 2 4
0 0
0 1
1 0
1 1

2
0
1
1
0