Problem:


Score : 900 points

Problem Statement

There is a tree with N vertices numbered 1 through N.
The i-th of the N-1 edges connects vertices a_i and b_i.

Initially, each vertex is uncolored.

Takahashi and Aoki is playing a game by painting the vertices. In this game, they alternately perform the following operation, starting from Takahashi:

Select a vertex that is not painted yet.

If it is Takahashi who is performing this operation, paint the vertex white; paint it black if it is Aoki.

Then, after all the vertices are colored, the following procedure takes place:

Repaint every white vertex that is adjacent to a black vertex, in black.

Note that all such white vertices are repainted simultaneously, not one at a time.

If there are still one or more white vertices remaining, Takahashi wins; if all the vertices are now black, Aoki wins.
Determine the winner of the game, assuming that both persons play optimally.

Constraints

2 ≤ N ≤ 10^5

1 ≤ a_i,b_i ≤ N

a_i ≠ b_i

The input graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

Print First if Takahashi wins; print Second if Aoki wins.

Sample Input 1

3
1 2
2 3

Sample Output 1

First

Below is a possible progress of the game:

First, Takahashi paint vertex 2 white.

Then, Aoki paint vertex 1 black.

Lastly, Takahashi paint vertex 3 white.

In this case, the colors of vertices 1, 2 and 3 after the final procedure are black, black and white, resulting in Takahashi's victory.

Sample Input 2

4
1 2
2 3
2 4

Sample Output 2

First

Sample Input 3

6
1 2
2 3
3 4
2 5
5 6

Sample Output 3

Second



Sample input:
3
1 2
2 3


Sample output:
First

Submission status: Wrong Answer

Solution code:
import queue
import sys

n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(lambda s: int(s) - 1, input().split())
    edges[a].append(b)
    edges[b].append(a)
q = queue.Queue()
leaf = -1
for index, ls in enumerate(edges):
    if len(ls) == 1:
        leaf = index
flag = [False for i in range(n)]
w = [False for i in range(n)]
q.put(leaf)
flag[leaf] = True
w[leaf] = True
while not q.empty():
    g = q.get()
    f = not w[g]
    for to in edges[g]:
        if flag[to]:
            continue
        q.put(to)
        flag[to] = True
        w[to] = f
        if not f:
            f = True
    if not f:
        print("First")
        sys.exit()

print("Second" if w.count(True) == w.count(False) else "First")

Submission status: Wrong Answer

Solution code:
import queue
import sys

n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(lambda s: int(s) - 1, input().split())
    edges[a].append(b)
    edges[b].append(a)
q = queue.Queue()
leaf = -1
for index, ls in enumerate(edges):
    if len(ls) == 1:
        leaf = index
flag = [False for i in range(n)]
w = [False for i in range(n)]
q.put(leaf)
flag[leaf] = True
w[leaf] = True
while not q.empty():
    g = q.get()
    f = not w[g]
    for to in edges[g]:
        if flag[to]:
            continue
        q.put(to)
        flag[to] = True
        w[to] = f
        if not f:
            f = True
    if not f:
        print("First")
        sys.exit()

print("Second")

Submission status: Wrong Answer

Solution code:
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)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
color = [0]*(n+1)
stack = [(1,1)]
while stack:
  x,c = stack.pop()
  color[x] = c
  for y in graph[x]:
    if color[y] == 0:
      stack.append((y,3-c))

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

Submission status: Wrong Answer

Solution code:
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)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
color = [0]*(n+1)
color[1] = 2
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("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
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("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
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[i]:
    if j%2 == 0:
      cnt += 1
  if cnt >= 2:
    flg = 1
if flg:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
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)]
parity = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    if dp[x].count(0) >= 2:
      flg = 1
    if 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)
stack2 = [root]
parity2 = [-1]*(n+1)
deg[root] -= 1
while stack2:
  x = stack2.pop()
  if dp[x].count(0) >= 2:
    flg = 1
  c0 = dp[x].count(0)
  c1 = dp[x].count(1)
  c2 = dp[x].count(2)
  for y in graph[x]:
    if deg[y] >= 1:
      deg[y] -= 1
      c00 = c0
      c11 = c1
      c22 = c2
      if c00 >= 2:
        flg = 1
      if parity[y] == 2:
        c22 -= 1
      elif parity[y] == 1:
        c11 -= 1
      elif parity[y] == 0:
        c00 -= 1
      if c22:
        parity2[x] = 2
      elif c11 and c00:
        parity2[x] = 2
      elif c11:
        parity2[x] = 0
      elif c00:
        parity2[x] = 1
      dp[y].append(parity2[x])
      stack2.append(y)
for i in range(1,n+1):
  if dp[i].count(0) >= 2:
    flg = 1
if flg:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
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)]
parity = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    if dp[x].count(0) >= 2:
      flg = 1
    if 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)
stack2 = [root]
parity2 = [-1]*(n+1)
deg[root] -= 1
while stack2:
  x = stack2.pop()
  if dp[x].count(0) >= 2:
    flg = 1
  c0 = dp[x].count(0)
  c1 = dp[x].count(1)
  c2 = dp[x].count(2)
  for y in graph[x]:
    if deg[y] >= 1:
      deg[y] -= 1
      c00 = c0
      c11 = c1
      c22 = c2
      if parity[y] == 2:
        c22 -= 1
      elif parity[y] == 1:
        c11 -= 1
      elif parity[y] == 0:
        c00 -= 1
      if c00 >= 2:
        flg = 1
      if c22:
        parity2[x] = 2
      elif c11 and c00:
        parity2[x] = 2
      elif c11:
        parity2[x] = 0
      elif c00:
        parity2[x] = 1
      dp[y].append(parity2[x])
      stack2.append(y)
if flg:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
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)]
parity = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    if dp[x].count(0) >= 2:
      flg = 1
    if 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)
stack2 = [root]
parity2 = [-1]*(n+1)
deg[root] -= 1
while stack2:
  x = stack2.pop()
  if dp[x].count(0) >= 2:
    flg = 1
  c0 = dp[x].count(0)
  c1 = dp[x].count(1)
  c2 = dp[x].count(2)
  for y in graph[x]:
    if deg[y] >= 1:
      deg[y] -= 1
      c00 = c0
      c11 = c1
      c22 = c2
      if parity[y] == 2:
        c22 -= 1
      elif parity[y] == 1:
        c11 -= 1
      elif parity[y] == 0:
        c00 -= 1
      if c00 >= 2:
        flg = 1
      if c22:
        parity2[x] = 2
      elif c11 and c00:
        parity2[x] = 2
      elif c11:
        parity2[x] = 0
      elif c00:
        parity2[x] = 1
      dp[y].append(parity2[x])
if flg:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
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)]
parity = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    if dp[x].count(0) >= 2:
      flg = 1
    if 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)
stack2 = [(root,0)]
parity2 = [-1]*(n+1)
deg[root] -= 1
while stack2:
  x,p = stack2.pop()
  if x == root:
    c0 = dp[x].count(0)
    c1 = dp[x].count(1)
    c2 = dp[x].count(2)
    for y in graph[x]:
      c00 = c0
      c11 = c1
      c22 = c2
      if parity[y] == 2:
        c22 -= 1
      elif parity[y] == 1:
        c11 -= 1
      elif parity[y] == 0:
        c00 -= 1
      if c00 >= 2:
        flg = 1
      if c22:
        parity2[x] = 2
      elif c11 and c00:
        parity2[x] = 2
      elif c11:
        parity2[x] = 0
      elif c00:
        parity2[x] = 1
      dp[y].append(parity2[x])
      deg[y] -= 1
      stack2.append((y,x))
  else:
    if dp[x].count(0) >= 2:
      flg = 1
    for y in graph[x]:
      if deg[y] >= 1:
        if dp[x][-1] == 2:
          parity2[x] = 2
        elif dp[x][-1] == 1:
          parity2[x] = 0
        elif dp[x][-1] == 0:
          parity2[x] = 1
        dp[y].append(parity2[x])
        deg[y] -= 1
        stack2.append((y,x))

      
if flg:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
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(18):
  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")

Submission status: Wrong Answer

Solution code:
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("Second")

Submission status: Wrong Answer

Solution code:
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
key = [0]*(n+1)
stack = []
root = 0
for i in range(1,n+1)[::-1]:
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
deg[root] += 1
dp = [[] for i in range(n+1)]
parity = [-1]*(n+1)
flg = 0
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")

Submission status: Wrong Answer

Solution code:
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
key = [0]*(n+1)
stack = []
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
deg[root] += 1
dp = [[] for i in range(n+1)]
parity = [-1]*(n+1)
flg = 0
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")

Submission status: Wrong Answer

Solution code:
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
key = [0]*(n+1)
for i in range(1,n+1):
  if deg[i]%2:
    for j in graph[i]:
      key[j] += 1
if max(key) >= 2:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
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
key = [0]*(n+1)
for i in range(1,n+1):
  if deg[i] == 1:
    for j in graph[i]:
      key[j] += 1
if max(key) >= 2:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    N = int(input())
    if N <= 3: return N & 1
    X = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        X[a-1].append(b-1)
        X[b-1].append(a-1)

    for i in range(N):
        if len(X[i]) > 1:
            break
    Q = [i]
    P = [-1] * N
    R = [i]
    while Q:
        i = Q.pop()
        for j in X[i]:
            if P[i] == j:
                X[i].remove(j)
                continue
            P[j] = i
            R.append(j)
            Q.append(j)
    
    isleaf = [0] * N
    for i in R[::-1]:
        if len(X[i]) == 0:
            isleaf[i] = 1
        else:
            if sum([isleaf[j] for j in X[i]]) > 1:
                return 1
        
    return 0

print("First" if main() else "Second")

Submission status: Wrong Answer

Solution code:
n = int(input())
if n == 2:
    print('Second')
    exit(0)
g = [[] for _ in range(n)]
ind = [0] * n
for _ in range(n - 1):
    a, b = map(int, input().split())
    ind[a - 1] += 1
    ind[b - 1] += 1
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
d = [-1] * n
prv = [-1] * n
for i in range(n):
    if ind[i] >= 2:
        s = [i]
        d[i] = 0
        break
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            prv[node] = p
            d[node] = 0
            s.append(node)
c = [0] * n
for i in range(n):
    if ind[i] == 1:
        c[prv[i]] += 1
for i in range(n):
    if c[i] >= 2:
        print('First')
        break
else:
    print('Second')

Submission status: Wrong Answer

Solution code:
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):
#    debug_print(maze)
    distance = [[inf]*w for _ in range(h)]
    def bfs():
        queue = deque()
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.popleft()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#'):
                    if distance[ny][nx]<=distance[y][x]+1:
                        continue
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)
#    for v in D:
#        print(v)
    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return


def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if W[ne] == -1:
                W[ne] = 0
                que.append(ne)
            if len(fordfs[now])==1:
                W[ne] +=1
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    W = bfs(N,0,V)
#    print(W)
    ans = "Second"
    for i in W:
        if i>=2:
            ans = "First"
            break
    if N%2==1:
        ans = "First"
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):
#    debug_print(maze)
    distance = [[inf]*w for _ in range(h)]
    def bfs():
        queue = deque()
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.popleft()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#'):
                    if distance[ny][nx]<=distance[y][x]+1:
                        continue
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)
#    for v in D:
#        print(v)
    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return


def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if W[ne] == -1:
                W[ne] = 0
                que.append(ne)
            if len(fordfs[now])==1:
                W[ne] +=1
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    W = bfs(N,0,V)
#    print(W)
    ans = "Second"
    for i in W:
        if i>=2:
            ans = "First"
            break
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist[node].append(W[i])
	W[node] += 1

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
	#例外処理
	if N == 2:
		print("Second")
		return

	judge = "Second"
	#DFS 判定
	#1回目
	W = [0] * N
	visit = ["No"] * N
	visit[0] = "Yes"
	Wlist = [[] for i in range(N)]
	DFS(G, W, Wlist, visit, 0)
	# print(Wlist)
	for i in range(N):
		# print(sum(Wlist[i]))
		cnt = 0
		jud = "Yes"
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
			if j % 2 == 0:
				jud = "No"
		if (N - 1 - sum(Wlist[i])) % 2 == 0 or Wlist[i] == []:
			jud = "No"
		if jud == "Yes":
			judge = "First"
		if cnt >= 2:
			judge = "First"
			break

	#2回目
	W = [0] * N
	visit = ["No"] * N
	visit[1] = "Yes"
	Wlist = [[] for i in range(N)]
	DFS(G, W, Wlist, visit, 1)
	for i in range(N):
		cnt = 0
		jud = "Yes"
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
			if j % 2 == 0:
				jud = "No"
		if (N - 1 - sum(Wlist[i])) % 2 == 0 or Wlist[i] == []:
			jud = "No"
		if jud == "Yes":
			judge = "First"
		if cnt >= 2:
			judge = "First"
			break

	#3回目
	W = [0] * N
	visit = ["No"] * N
	visit[2] = "Yes"
	Wlist = [[] for i in range(N)]
	DFS(G, W, Wlist, visit, 2)
	for i in range(N):
		cnt = 0
		jud = "Yes"
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
			if j % 2 == 0:
				jud = "No"
		if (N - 1 - sum(Wlist[i])) % 2 == 0 or Wlist[i] == []:
			jud = "No"
		if jud == "Yes":
			judge = "First"
		if cnt >= 2:
			judge = "First"
			break

	if N % 2 == 1:
		judge = "First"
	
	print(judge)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist[node].append(W[i])
	W[node] += 1

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
	#例外処理
	if N == 2:
		print("Second")
		return

	judge = "Second"
	#DFS 判定
	#1回目
	W = [0] * N
	visit = ["No"] * N
	visit[0] = "Yes"
	Wlist = [[] for i in range(N)]
	DFS(G, W, Wlist, visit, 0)
	# print(Wlist)
	for i in range(N):
		# print(sum(Wlist[i]))
		cnt = 0
		jud = "Yes"
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
			if j % 2 == 0:
				jud = "No"
		if (N - 1 - sum(Wlist[i])) % 2 == 0 or Wlist[i] == []:
			jud = "No"
		if jud == "Yes":
			judge = "First"
		if cnt >= 2:
			judge = "First"
			break

	#2回目
	W = [0] * N
	visit = ["No"] * N
	visit[1] = "Yes"
	Wlist = [[] for i in range(N)]
	DFS(G, W, Wlist, visit, 1)
	for i in range(N):
		cnt = 0
		jud = "Yes"
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
			if j % 2 == 0:
				jud = "No"
		if (N - 1 - sum(Wlist[i])) % 2 == 0 or Wlist[i] == []:
			jud = "No"
		if jud == "Yes":
			judge = "First"
		if cnt >= 2:
			judge = "First"
			break

	#3回目
	W = [0] * N
	visit = ["No"] * N
	visit[2] = "Yes"
	Wlist = [[] for i in range(N)]
	DFS(G, W, Wlist, visit, 2)
	for i in range(N):
		cnt = 0
		jud = "Yes"
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
			if j % 2 == 0:
				jud = "No"
		if (N - 1 - sum(Wlist[i])) % 2 == 0 or Wlist[i] == []:
			jud = "No"
		if jud == "Yes":
			judge = "First"
		if cnt >= 2:
			judge = "First"
			break

	print(judge)

if __name__ == '__main__':
	main()