結果

問題 No.3056 Disconnected Coloring
コンテスト
ユーザー ゼット
提出日時 2025-03-14 22:11:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 616 ms / 2,000 ms
コード長 1,751 bytes
コンパイル時間 411 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 127,308 KB
最終ジャッジ日時 2025-03-14 22:11:35
合計ジャッジ時間 14,071 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M=map(int,input().split())
G=[[] for i in range(N+1)]
if M%2==1:
  print(-1)
  exit()
for i in range(M):
  x,y=map(int,input().split())
  if x>y:
    x,y=y,x
  if x==1 and y==N:
    print(-1)
    exit()
  G[y].append((x,i))
  G[x].append((y,i))
c=0
result=['B']*M
used=[False]*(N+1)
from collections import deque
if len(G[1])<=M//2:
  used[1]=True
  S=deque()
  S.append(1)
  while S:
    if c==M//2:
      break
    x=S.pop()
    for B in G[x]:
      y,pos=B[:]
      if result[pos]=='R':
        continue
      if y==N:
        continue
      c+=1
      result[pos]='R'
      if c==M//2:
        break
      if used[y]==False:
        used[y]=True
        S.append(y)
  S=deque()
  S.append(N)
  p=[False]*(N+1)
  p[N]=True
  while S:
    if c==M//2:
      break
    x=S.pop()
    for B in G[x]:
      y,pos=B[:]
      if result[pos]=='R':
        continue
      if used[y]==True:
        continue
      c+=1
      result[pos]='R'
      if c==M//2:
        break
      if p[y]==False:
        p[y]=True
        S.append(y)
else:
  used[N]=True
  S=deque()
  S.append(N)
  while S:
    if c==M//2:
      break
    x=S.pop()
    for B in G[x]:
      y,pos=B[:]
      if result[pos]=='R':
        continue
      if y==1:
        continue
      c+=1
      result[pos]='R'
      if c==M//2:
        break
      if used[y]==False:
        used[y]=True
        S.append(y)
  S=deque()
  S.append(1)
  p=[False]*(N+1)
  p[1]=True
  while S:
    if c==M//2:
      break
    x=S.pop()
    for B in G[x]:
      y,pos=B[:]
      if result[pos]=='R':
        continue
      if used[y]==True:
        continue
      c+=1
      result[pos]='R'
      if c==M//2:
        break
      if p[y]==False:
        p[y]=True
        S.append(y)
print(*result,sep='')
0