結果

問題 No.1640 簡単な色塗り
ユーザー convexineq
提出日時 2021-08-06 22:59:23
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 822 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 110,300 KB
最終ジャッジ日時 2024-06-29 16:04:31
合計ジャッジ時間 18,794 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
deg = [0]*n
g = [[] for _ in range(n)]
edges = []
for i in range(n):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    g[a].append((b,i))
    g[b].append((a,i))
    edges.append((a,b,i))

used = [0]*n
ans = [-1]*n
q = [i for i in range(n) if deg[i] == 1]
while q:
    v = q.pop()
    for c,i in g[v]:
        if used[i]: continue
        deg[c] -= 1
        used[i] = 1
        ans[i] = v
        if deg[c] == 1:
            q.append(c)

edges.sort(key=lambda x:x[0])
for a,b,i in edges:
    if used[i]: continue
    if (deg[a] == 2 and deg[b] == 2) or deg[a] == 1:
        ans[i] = a
        deg[b] -= 1
    else:
        ans[i] = b
        deg[a] -= 1

if sorted(ans) == list(range(n)):
    print("Yes")
    for i in ans: print(i+1)
else:
    print("No")
0