Problem p03726 (python)

Fixed submission:

import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
if n == 2:
  print("Second")
  exit()
stack = []
root = 0
for i in range(1,n+1)[::-1]:
  if deg[i] == 1:
    stack.append(i)
  else:
    root = i
flg = 0
deg[root] += 1
dp = [[] for i in range(n+1)]
dist = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    if dp[x].count(0)>=2:
      flg = 1
    if dp[x].count(0):
      dist[x] = 1
    else:
      dist[x] = 0
  else:
    dist[x] = 0
  for y in graph[x]:
    if deg[y] >= 2:
      dp[y].append(dist[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg or dist[root]==0:
  print("First")
else:
  print("Second")

Buggy submission (verdict: Runtime Error):
import sys
import random
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
color = [0]*(n+1)
color[1] = 1
stack = [1]
while stack:
  x = stack.pop()
  for y in graph[x]:
    if color[y] == 0:
      color[y] = 3-color[x]
      stack.append(y)

if color.count(1) != color.count(2):
  print(2/0)
  print("First")
else:
  print("Second")

Buggy submission (verdict: Runtime Error):
import sys
import random
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
if n == 2:
  print("Second")
  exit()
stack = []
root = 0
for i in range(1,n+1)[::-1]:
  if deg[i] == 1:
    stack.append(i)
  else:
    root = i
flg = 0
deg[root] += 1
dp = [[] for i in range(n+1)]
dist = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    dist[x] = min(dp[x])+1
  else:
    dist[x] = 0
  for y in graph[x]:
    if deg[y] >= 2:
      dp[y].append(dist[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
stack2 = [root]
dist2 = [-1]*(n+1)
deg[root] -= 1
d = dist[x]
while stack2:
  x = stack2.pop()
  dp[x].sort()
  for y in graph[x]:
    if deg[y] >= 1:
      if dist[y] != dp[x][0]:
        dp[y].append(dp[x][0]+1)
      else:
        dp[y].append(dp[x][1]+1)
      deg[y] -= 1
      stack2.append(y)
for i in range(1,n+1):
  cnt = 0
  for j in dp:
    if j%2:
      cnt += 1
  if cnt >= 2:
    flg = 1
if flg:
  print("First")
else:
  print("Second")

Buggy submission (verdict: Runtime Error):
import sys
import random
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
degorigin = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  degorigin[a] += 1
  degorigin[b] += 1
if n == 2:
  print("Second")
  exit()
stackorigin = []
root = 0
candidate = []
for i in range(1,n+1)[::-1]:
  if degorigin[i] == 1:
    stackorigin.append(i)
  else:
    candidate.append(i)
flg = 0
for _ in range(1):
  if flg:
    break
  stack = stackorigin[:]
  deg = degorigin[:]
  root = candidate[random.randint(0,len(candidate)-1)]
  deg[root] += 1
  dp = [[] for i in range(n+1)]
  parity = [-1]*(n+1)
  while stack:
    x = stack.pop()
    if dp[x]:
      if dp[x].count(0) >= 2:
        flg = 1
        break
      elif dp[x].count(2):
        parity[x] = 2
      elif dp[x].count(1) and dp[x].count(0):
        parity[x] = 2
      elif dp[x].count(1):
        parity[x] = 0
      elif dp[x].count(0):
        parity[x] = 1
    else:
      parity[x] = 0
    for y in graph[x]:
      if deg[y] >= 2:
        dp[y].append(parity[x])
        deg[y] -= 1
        if deg[y] == 1:
          stack.append(y)
if flg:
  print(2/0)
  print("First")
else:
  print("Second")

Buggy submission (verdict: Runtime Error):
import sys
import random
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
degorigin = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  degorigin[a] += 1
  degorigin[b] += 1

stackorigin = []
root = 0
candidate = []
for i in range(1,n+1)[::-1]:
  if degorigin[i] == 1:
    stackorigin.append(i)
  else:
    candidate.append(i)
flg = 0
for _ in range(10):
  if flg:
    break
  stack = stackorigin[:]
  deg = degorigin[:]
  root = candidate[random.randint(0,len(candidate)-1)]
  deg[root] += 1
  dp = [[] for i in range(n+1)]
  parity = [-1]*(n+1)
  while stack:
    x = stack.pop()
    if dp[x]:
      if dp[x].count(0) >= 2:
        flg = 1
        break
      elif dp[x].count(2):
        parity[x] = 2
      elif dp[x].count(1) and dp[x].count(0):
        parity[x] = 2
      elif dp[x].count(1):
        parity[x] = 0
      elif dp[x].count(0):
        parity[x] = 1
    else:
      parity[x] = 0
    for y in graph[x]:
      if deg[y] >= 2:
        dp[y].append(parity[x])
        deg[y] -= 1
        if deg[y] == 1:
          stack.append(y)
if flg:
  print("First")
else:
  print("Second")

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
key = [0]*(n+1)
stack = deque()
root = 0
for i in range(1,n+1)[::-1]:
  if deg[i] == 1:
    stack.append(i)
  else:
    deg[i] += 1
dp = [[] for i in range(n+1)]
seen = 0
parity = [-1]*(n+1)
flg = 0
seen = len(stack)
while stack:
  x = stack.popleft()
  if dp[x]:
    if dp[x].count(0) >= 2:
      flg = 1
      break
    elif dp[x].count(2):
      parity[x] = 2
    elif dp[x].count(1) and dp[x].count(0):
      parity[x] = 2
    elif dp[x].count(1):
      parity[x] = 0
    elif dp[x].count(0):
      parity[x] = 1
  else:
    parity[x] = 0
  for y in graph[x]:
    if (seen < n-1 and deg[y] >= 3) or (seen == n-1 and deg[y] >= 2):
      dp[y].append(parity[x])
      deg[y] -= 1
      if (seen < n-1 and deg[y] == 2) or (seen == n-1 and deg[y] == 1):
        stack.append(y)
        seen += 1
if flg:
  print("First")
else:
  print(2/0)
  print("Second")