結果

問題 No.3552 Triangular Coloring
コンテスト
ユーザー 👑 loop0919
提出日時 2026-05-09 01:02:39
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,647 ms / 2,000 ms
コード長 920 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 359 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 249,700 KB
最終ジャッジ日時 2026-05-22 21:49:32
合計ジャッジ時間 14,859 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

INF = 10**18

N, M = [int(s) for s in input().split()]
graph = [[] for _ in range(N)]

if N == 3:
    print("Yes")
    print(*[1, 2, 3])
    exit()

for _ in range(M):
    u, v = [int(s) - 1 for s in input().split()]
    graph[u].append(v)
    graph[v].append(u)

del_graph = [set(graph[v]) for v in range(N)]
three = [v for v in range(N) if len(graph[v]) == 3]

order = []
connected = []

while three:
    curr = three.pop()
    order.append(curr)
    to_vs = del_graph[curr].copy()

    connected.append(to_vs)

    for to in to_vs:
        del_graph[to].discard(curr)

        if len(del_graph[to]) == 3:
            three.append(to)

order = order[::-1]
connected = connected[::-1]

answers = [None] * N
answers[order[0]] = 1
answers[order[1]] = 2
answers[order[2]] = 3

for curr, vs in zip(order[3:], connected[3:]):
    answers[curr] = ({1, 2, 3, 4} - {answers[v] for v in vs}).pop()

print("Yes")
print(*answers)
0