이분 그래프의 간선 색칠

$L + R$개의 정점과 $M$개의 간선으로 이루어진 무방향 이분 그래프가 주어진다. $i$번째 간선은 $(a_i, b_i)$이다.

간선 색칠 수를 달성하는 적절한 간선 색칠을 구한다.

제약 조건

• $1 \leq L, R \leq 100000$
• $1 \leq M \leq 100000$
• $0 \leq a_i < L$
• $0 \leq b_i < R$

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

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

$K$은 간선 색칠 수이고, $c_i$는 i번째 간선의 색을 나타내는 정수이다. $c_i$는 $0 \leq c_i < K$을 만족해야 한다.