結果

問題 No.3552 Triangular Coloring
コンテスト
ユーザー tassei903
提出日時 2026-05-26 21:57:33
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 782 ms / 2,000 ms
コード長 1,168 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,491 ms
コンパイル使用メモリ 84,464 KB
実行使用メモリ 157,024 KB
最終ジャッジ日時 2026-05-26 21:57:43
合計ジャッジ時間 9,725 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
# input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
"""
1^2^3 = 0
0^2^3 = 1
0^1^3 = 2
0^1^2 = 3


"""

n, m = na()

g = [[] for i in range(n)]
for _ in range(m):
    x, y = na()
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

q = []
deg = [len(g[i]) for i in range(n)]

ok = [0] * n
for i in range(n):
    if deg[i] == 3:
        q.append(i)


par = [[] for i in range(n)]

et = []

while q:
    x = q.pop()
    if deg[x] != 3:
        continue
    ok[x] = 1
    et.append(x)
    for y in g[x]:
        if ok[y]:
            continue
        par[x].append(y)
        deg[y] -= 1
        if deg[y] == 3:
            q.append(y)
ans = [-1] * n
t = 0
for i in range(n):
    if ok[i] == 0:
        ans[i] = t
        t += 1

# print(et)
for i in et[::-1]:
    s = 0
    for j in par[i]:
        s ^= ans[j]
    ans[i] = s
Yes()
print(*[x + 1 for x in ans])
0