题目背景

翻译自 CSES-1683 题。

题目描述

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

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示行星的数量和传送门的数量。行星编号为 $1,2,\ldots,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 \le n \le 10^5$；
• $1 \le m \le 2 \cdot 10^5$；
• $1 \le a,b \le n$。