You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1683 题。

题目描述

一个游戏中有 $n$ 个行星，通过 $m$ 条传送门连接。两个行星 $a$ 和 $b$ 属于同一个王国，当且仅当存在一条路径从 $a$ 到 $b$ 且从 $b$ 到 $a$。你的任务是确定每个行星所属的王国。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示行星的数量和传送门的数量。行星编号为 $1,2,…,n$。

接下来有 $m$ 行，每行包含两个整数 $a$ 和 $b$：表示从行星 $a$ 可以通过传送门到达行星 $b$。

输出格式

首先输出一个整数 $k$：表示王国的数量。

然后，对于每个行星，输出一个王国标签，标签范围在 $1$ 到 $k$ 之间。你可以输出任何有效的解。

样例

5 6
1 2
2 3
3 1
3 4
4 5
5 4

2
1 1 1 2 2

说明/提示

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2 \cdot 10^5$

$1 \leq a, b \leq n$。