题目描述

给定一张 $n$ 个点、$m$ 条边的无向图，结点编号 $1\sim n$。图中允许多重边与自环，且图不一定连通。

如果能够把所有点分成两个集合，使得每条边的两个端点分别落在不同集合中，就称这张图是二分图。请你判断这张图是不是二分图；如果是，再给出一组具体的染色方案。

输入格式

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

接下来 $m$ 行，每行两个整数 $u,v$，表示一条连接 $u$ 与 $v$ 的无向边。

输出格式

如果不是二分图，输出一行 NO。

如果是二分图，第一行输出 YES。

第二行输出 $n$ 个整数，第 $i$ 个数为结点 $i$ 的颜色（$0$ 或 $1$）。为了统一答案，规定：按编号从小到大扫描，遇到尚未染色的点就把它染成 $0$，然后用 BFS 传播颜色（于是每个连通块中编号最小的点颜色都是 $0$）。

输入输出样例 #1

输入 #1

4 4
1 2
2 3
3 1
4 3

输出 #1

NO

输入输出样例 #2

输入 #2

5 4
1 2
2 3
3 4
1 5

输出 #2

YES
0 1 0 1 1

说明

数据范围

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