結果

問題 No.3056 Disconnected Coloring
ユーザー ゼット
提出日時 2025-03-14 22:01:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,065 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 123,956 KB
最終ジャッジ日時 2025-03-14 22:01:33
合計ジャッジ時間 14,474 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 WA * 9
権限があれば一括ダウンロードができます

ソースコード

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[N])>M//2:
  for B in G[N]:
    y,pos=B[:]
    result[pos]='R'
    c+=1
    if c==M//2:
      break
  print(*result,sep='')
  exit()
if len(G[1])>M//2:
  for B in G[1]:
    y,pos=B[:]
    result[pos]='R'
    c+=1
    if c==M//2:
      break
  print(*result,sep='')
  exit()
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==N:
        continue
      c+=1
      if c==M//2:
        break
      result[pos]='R'
      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
      if c==M//2:
        break
      result[pos]='R'
      if c==M//2:
        break
      if p[y]==False:
        p[y]=True
        S.append(y)
print(*result,sep='')
0