結果

問題 No.3056 Disconnected Coloring
ユーザー SPD_9X2
提出日時 2024-10-26 19:09:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 713 ms / 2,000 ms
コード長 1,779 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,140 KB
実行使用メモリ 132,628 KB
最終ジャッジ日時 2025-03-14 19:59:43
合計ジャッジ時間 14,430 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/11508

辺の本数が奇数なら自明に不可能
直接結ぶ辺がある場合も不可能
辺はN-1本以上

偶数の場合
1,N どちらも接続辺が半数以下の場合、それぞれに接続する辺を赤・青で塗ればいい
そうでない場合、不可能か…？

半分以上の辺を片方が占めている場合
できる場合はある -> ウニにちょっと付け足した場合など

多重辺がないなら
過半数

"""

import sys
from collections import deque

N,M = map(int,input().split())

if M % 2 == 1:
    print (-1)
    sys.exit()

lis = [ [] for i in range(N) ]

for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1

    lis[u].append( (v,i) )
    lis[v].append( (u,i) )

    if u == 0 and v == N-1:
        print (-1)
        sys.exit()

reach1 = [False] * M
reachN = [False] * M

q = deque([0])
vlis = [False] * N
vlis[0] = True
while q:
    v = q.popleft()
    for nex,eidx in lis[v]:
        reach1[eidx] = True
        if vlis[nex] == False and nex != N-1:
            q.append( nex )
            vlis[nex] = True

q = deque([N-1])
vlis = [False] * N
vlis[N-1] = True
while q:
    v = q.popleft()
    for nex,eidx in lis[v]:
        reachN[eidx] = True
        if vlis[nex] == False and nex != 0:
            q.append( nex )
            vlis[nex] = True

blue = M // 2
red = M // 2

ans = [None] * M

for _,eidx in lis[0]:
    if reachN[eidx]:
        ans[eidx] = "B"
        blue -= 1

for _,eidx in lis[N-1]:
    if reach1[eidx]:
        ans[eidx] = "R"
        red -= 1

for j in range(M):

    if ans[j] == None:
        if red > 0:
            ans[j] = "R"
            red -= 1
        else:
            ans[j] = "B"
            blue -= 1

print (*ans,sep="")
0