Submission #6386296

---

Source Code Expand

import collections

def printCircuit(v):
  edge_count=[0]*(n+1)
  for i in range(1,n+1):
    edge_count[i]=len(g[i])
  curr_path=collections.deque()
  circuit=[]
  curr_path.appendleft(v)
  curr_v=v
  while len(curr_path)!=0:
    if edge_count[curr_v]:
      curr_path.appendleft(curr_v)
      next_v=g[curr_v].pop(-1)
      g[next_v].remove(curr_v)
      edge_count[curr_v]-=1
      edge_count[next_v]-=1
      curr_v=next_v
    else:
      circuit.append(curr_v)
      curr_v=curr_path.popleft()
  return circuit

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
cnt=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
  cnt[a]+=1
  cnt[b]+=1
cnt1=0
cnt2=0
cand=[]
for i in range(1,n+1):
  if cnt[i]%2==0:
    cnt1+=1
  else:
    cnt2+=1
    cand.append(i)
if m%2==1:
  print(-1)
  else:
  if cnt1==n:
    path=printCircuit(1)
    if len(path)%2==1:
      for i in range(len(path)):
        if i%2==1:
          print(path[i],path[i-1])
          print(path[i],path[i+1])
    else:
      print(-1)
  elif cnt1==n-2 and cnt2==2:
    if len(g[cand[0]])==1:
      c=cand[0]
    else:
      c=cand[1]
    path=printCircuit(c)
    if len(path)%2==1:
      for i in range(len(path)):
        if i%2==1:
          print(path[i],path[i-1])
          print(path[i],path[i+1])
    else:
      print(-1)
  else:
    print(-1)

Submission Info

Judge Result