問題一覧 > 教育的問題

No.8071 Iridescent Coloring

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 2
作問者 : 37zigen / テスター : opt
お気に入りにしたユーザー ProblemId : 4724 / 自分の提出
問題文最終更新日: 2020-07-27 23:30:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

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もしくは右上の雲マークをクリックしてアカウントを作成してください。