题目描述

给定一张 $n$ 个点、$m$ 条边的有向图，结点编号 $1\sim n$。图中可能有重边，也可能有自环。

如果一个点集中的任意两个点都能互相到达，就称这个点集是一个强连通分量（极大强连通子图）。请你求出这张图的强连通分量个数，并给出每个点所属的分量编号。

编号规则：把每个分量中编号最小的点拿出来，按这个最小值从小到大排序，依次编号为 $1,2,\dots,k$。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $u,v$，表示一条从 $u$ 指向 $v$ 的有向边。

输出格式

第一行一个整数 $k$，表示强连通分量个数。

第二行 $n$ 个整数，第 $v$ 个数表示结点 $v$ 所属的分量编号。

输入输出样例 #1

输入 #1

5 4
1 2
2 3
3 1
4 5

输出 #1

3
1 1 1 2 3

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$0\le m\le 5\times 10^5$。