No.8071 Iridescent Coloring
Problem Statement
You are given a bipartite graph whose parts $V_1,V_2$ have $L,R$ vertices respectively and which has $M$ edges.
The $i$-th edge connects vertex $a_i$ of $V_1$ and vertex $b_i$ of $V_2$.
Among the edge colorings in which the set of colors of the edges incident to each vertex is the same for all vertices, construct one that uses the maximum number of colors (★).
Let us restate ★ in rigorous terms. An edge coloring of a graph $ G=(V,E)$ is a surjective map $ c:E \rightarrow S$. Among these, consider the edge colorings $c$ such that $\{ c(e) \mid e \in E(u) \}=\{ c(e) \mid e \in E(v) \}$ holds for any vertices $u,v$ (where $E(v)$ is the set of edges incident to vertex $v$).
Construct a $c$ that maximizes $|S|$ (we will call this coloring an iridescent coloring).
Input
$L$ $R$ $M$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$
There are no isolated vertices.
$1 \leq L,R \leq 1000$
$1 \leq M \leq 10000$
$0 \leq a_i < L$
$0 \leq b_i < R$
Test cases for experts that do not affect AC (evil cases)
$1 \leq L,R \leq 100000$
$1 \leq M \leq 100000$
Output
$K$
$c_1$
$\vdots$
$c_{M}$
$K$ is the number of colors, and $c_i$ is an integer representing the color of the $i$-th edge. $c_i$ must satisfy $0 \leq c_i < K$. If there are multiple colorings satisfying the conditions, you may output any of them.
Sample
Sample 1
Input
1 1 1 0 0
Output
1 0
Sample 2
Input
1 3 3 0 0 0 1 0 2
Output
1 0 0 0
Sample 3
Input
2 2 4 0 0 0 1 1 0 1 1
Output
2 0 1 1 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
37zigen
opt