3 super coloring

그래프의 정점들을 색칠하는 보통의 coloring 문제는 많이 알려져 있다. 하지만 형진이는 그것이 지루해져, 새로운 방식의 색칠법인 super coloring을 고안했다.

어떤 그래프의 super coloring은 각 정점에 색을 칠하는 방법으로, 서로 다른 두 정점 $u, v$에 대해 다음 조건을 만족해야 한다.

• $u$와 $v$가 간선으로 연결되어 있으면, 두 정점의 색은 서로 달라야 한다.
• $u$와 $v$가 간선으로 연결되어 있지 않으면, 두 정점의 색은 서로 같아야 한다.

이후 형진이는 그래프 자체도 새롭게 정의해 보기로 했다. 주어진 그래프에서 원래 있던 모든 간선은 제거하고, 원래 없던 모든 간선은 새로 추가한 그래프를 반대 그래프라고 하자. 단, 자기 자신으로 가는 간선은 고려하지 않는다.

형진이는 주어진 그래프의 반대 그래프가 $3$개의 색만으로 super coloring 가능한지 궁금해졌다.

반대 그래프를 $3$개의 색으로 super coloring할 수 있는지 판별하고, 가능하다면 그 색칠 방법도 함께 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$n\ m$ $u_1\ v_1$ $u_2\ v_2$ $\cdots$ $u_m\ v_m$

주어지는 그래프는 $n$개의 정점과 $m$개의 간선을 가진 단순 무방향 그래프이다. 정점은 $1$번부터 $n$번까지 번호가 매겨져 있다.

반대 그래프의 super coloring이 가능하다면 첫째 줄에 yes를 출력한다. 불가능하다면 첫째 줄에 no를 출력한다.

가능한 경우, 둘째 줄에 $n$개의 정수 $c_1, c_2, \ldots, c_n$을 공백으로 구분하여 출력한다. $c_i$는 $i$번 정점의 색이며, $1$, $2$, $3$ 중 하나여야 한다.

가능한 색칠 방법이 여러 가지라면 아무거나 출력해도 된다.

• $1 \le n \le 200\,000$.
• $0 \le m \le 200\,000$.
• $1 \le u_i, v_i \le n$.
• $u_i \ne v_i$.
• 같은 간선은 두 번 이상 주어지지 않는다.