問題一覧 > 通常問題

No.3552 Triangular Coloring

レベル : / AI推定難易度 : 1350 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 36
作問者 : ぽえ / テスター : yimiya(いみや) 👑 loop0919 lif4635 ルク はるるん
お気に入りにしたユーザー ProblemId : 13285 / 自分の提出
問題文最終更新日: 2026-08-20 08:58:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 500 (順位表) の他の問題:

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.

  1. 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.
  2. 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.
  3. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。