题目描述

给你一个包含 $n$ 个节点 $m$ 条边的有向图。节点编号从 $1$ 到 $n$。

求图中：

1. 强连通分量的个数；
2. 每个节点所在的强连通分量内编号最小的那个节点的编号。

输入格式

第一行，两个整数 $n$ 和 $m$，以一个空格分隔（$1 \le n \le 10^5, 0 \le m \le \min(2 \cdot 10^5, n(n-1))$）。

接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，以一个空格分隔，表示存在一条以节点 $a$ 为起点，以节点 $b$ 为终点的有向边（$1 \le a, b \le n$，$a \neq b$，且不存在相同的数对 $(a, b)$）。

输出格式

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

第二行，$n$ 个整数，两两之间以一个空格分隔。其中第 $i$ 个整数表示节点 $i$ 所在的强连通分量中编号最小的那个节点的编号。

样例

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

3
1 1 3 1 1 6