No.3552 Triangular Coloring
Problem Statement
You are given a planar graph with $N$ vertices and $M$ edges.
Determine whether the vertices can be colored using the colors $1, 2, 3, 4$ so that any two vertices directly connected by an edge of this graph have different colors, and if they can, output such a coloring.
Here, the graph was generated under the following conditions.
- There is a graph with $3$ vertices and $3$ edges in which the vertices are all connected to one another. Initially, the vertices are not numbered.
- Repeat the following operation $N-3$ times.
- Choose one triangular face in the graph.
- Add one point inside the face, and connect it by an edge to each of the three vertices of the chosen face.
- Number the vertices from $1$ to $N$.
Definition of a triangular face (click to expand)
The edges of a planar graph divide the plane into several regions.
Each of these regions is called a face. The region extending infinitely on the outside is called the outer face.
Among the faces other than the outer face, one whose boundary consists of $3$ edges is defined as a triangular face.
Constraints
- All input values are integers.
- $3 \le N \le 2 \times 10^5$
- $M = 3N - 6$
- $1 \le u_i, v_i \le N$
- The given graph is guaranteed to have been generated under the conditions in the problem statement.
Input
The input is given from standard input in the following format.
$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
Output
If no coloring satisfying the condition exists, output No.
If the condition can be satisfied by painting each vertex $v ~ (1 \leq v \leq N)$ with color $C_v$, output in the following format.
Yes $C_1$ $C_2$ $\ldots$ $C_N$
If there are multiple solutions, any of them will be accepted.
Sample
Sample 1
Input
5 9 1 2 2 3 3 1 1 4 2 4 3 4 1 5 2 5 3 5
Output
Yes 1 2 3 4 4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ぽえ
yimiya(いみや)