問題文

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

★を厳密な表現に言い換えよう。グラフ$ G=(V,E)$の辺着色とは全射な写像 $ c:E \rightarrow 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$
$\vdots$
$a_M$ $b_M$

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

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

出力

$K$
$c_1$
$\vdots$
$c_{M}$

$K$ は色数、$c_i$ は $i$ 番目の辺の色を表す整数。$c_i$ は $0 \leq 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