← 返回题目

题库练习 Coloring Edges

← 上一题下一题 →

A12957 | $Coloring Edges$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given a directed graph with $n$ vertices and $m$ directed edges without self-loops or multiple edges. Let's denote the $k$ -coloring of a digraph as following: you color each edge in one of $k$ colors. The $k$ -coloring is good if and only if there no cycle formed by edges of same color. Find a good $k$ -coloring of given digraph with minimum possible $k$ .

输入格式

The first line contains two integers $n$ and $m$ ( $2 \le n \le 5000$ , $1 \le m \le 5000$ ) — the number of vertices and edges in the digraph, respectively. Next $m$ lines contain description of edges — one per line. Each edge is a pair of integers $u$ and $v$ ( $1 \le u, v \le n$ , $u \ne v$ ) — there is directed edge from $u$ to $v$ in the graph. It is guaranteed that each ordered pair $(u, v)$ appears in the list of edges at most once.

输出格式

In the first line print single integer $k$ — the number of used colors in a good $k$ -coloring of given graph. In the second line print $m$ integers $c_1, c_2, \dots, c_m$ ( $1 \le c_i \le k$ ), where $c_i$ is a color of the $i$ -th edge (in order as they are given in the input). If there are multiple answers print any of them (you still have to minimize $k$ ).

输入输出样例

输入 #1

输出 #1

1
1 1 1 1 1

输入 #2

输出 #2

2
1 1 2

C++ 编辑器

输入

输出