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:
n=int(input())
if n==1:print("First");exit()
if n==2:print("Second");exit()
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
matched=[0]*n
leaf=[]
for i in range(n):
    if len(graph[i])==1:
        leaf.append(i)
for i in leaf:
    matched[i]+=1
    matched[graph[i][0]]+=1
for i in range(n):
  if matched[i]!=1:print("First");exit()
print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First");exit()
if n==2:print("Second");exit()
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
matched=[False]*n
leaf=[]
for i in range(n):
    if len(graph[i])==1:
        leaf.append(i)
for i in leaf:
    matched[i]=True
    matched[graph[i][0]]=True
if False in matched:print("First")
else:print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First");exit()
if n==2:print("Second");exit()
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
matched=[False]*n
leaf=[]
for i in range(n):
    if len(graph[i])==1:
        leaf.append(i)
for i in leaf:
    if matched[graph[i][0]]:print("First");exit()
    matched[i]=True
    matched[graph[i][0]]=True
if False in matched:print("First")
else:print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First");exit()
if n==2:print("Second");exit()
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
matched=[False]*n
leaf=[]
for i in range(n):
    if len(graph[i])==1:
        leaf.append(i)
for i in leaf:
    if matched[graph[i][0]]:print("First");exit()
    matched[i]=True
    matched[graph[i][0]]=True
print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First");exit()
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
matched=[False]*n
for i in range(n):
    if matched[i]:continue
    if len(graph[i])==1:
        if matched[graph[i][0]]:print("First");exit()
        matched[i]=True;matched[graph[i][0]]=True
print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First");exit()
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
matched=[False]*n
for i in range(n):
    if matched[i]:continue
    if len(graph[i])==1:
        if matched[i] or matched[graph[i][0]]:print("First");exit()
        matched[i]=True;matched[graph[i][0]]=True
print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First");exit()
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
leaves=0
leafcnt=[0]*n
for i in range(n):
    if len(graph[i])==1:
        leaves+=1
        leafcnt[graph[i][0]]+=1
for i in range(n):
    if leafcnt[i]>=2:
        print("First")
        exit()
if n%2 == 1:print("First")
else:print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First")
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
matched=[0]*n
for i in range(n):
    if len(graph[i])==1:
        if matched[i] == 2 or matched[graph[i][0]] == 2:print("First");exit()
        matched[i]+=1;matched[graph[i][0]]+=1
print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First")
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
leaves=0
leafcnt=[0]*n
for i in range(n):
    if len(graph[i])==1:
        leaves+=1
        leafcnt[graph[i][0]]+=1
for i in range(n):
    if leafcnt[i]>=2:
        print("First")
        exit()
if n%2 == 0 and leaves== n//2:print("Second")
else:print("First")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First")
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
leaves=0
leafcnt=[0]*n
for i in range(n):
    if len(graph[i])==1:
        leaves+=1
        leafcnt[graph[i][0]]+=1
for i in range(n):
    if leafcnt[i]>=2:
        print("First")
        exit()
if n%2 == 0 and leaves== n//2:print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First")
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
leaves=0
leafcnt=[0]*n
for i in range(n):
    if len(graph[i])==1:
        leaves+=1
        leafcnt[graph[i][0]]+=1
for i in range(n):
    if leafcnt[i]>=2:
        print("First")
        exit()
if n%2 == 1:print("First")
else:print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:print("First")
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
isleaf=[False]*n
leafcnt=[0]*n
for i in range(n):
    if len(graph[i])==1:
        isleaf[i]=True
        leafcnt[graph[i][0]]+=1
for i in range(n):
    if leafcnt[i]>=2:
        print("First")
        exit()
print("Second")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

q = []
checked = [-1]*N
for n in range(N):
    if len(graph[n]) == 1:
        q.append(n)
        checked[n] = 0

ok = False
while q:
    posiq = []
    for p in q:
        update = False
        for np in graph[p]:
            if checked[np] == -1:
                checked[np] = checked[p] + 1
                update = True
                posiq.append(np)
            elif checked[np] == checked[p] + 1:
                ok = True
                break
            elif checked[np] == checked[p]:
                update = True
        if not update:
            ok = True
            break
    
    q = []
    for p in posiq:
        for np in graph[p]:
            if checked[np] == -1:
                c = 0
                for mp in graph[np]:
                    if checked[mp] == -1:
                        c += 1
                    if c >= 2: break
                if c <= 1:
                    q.append(np)
    for np in q:
        checked[np] = checked[p] + 1

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

q = []
checked = [-1]*N
for n in range(N):
    if len(graph[n]) == 1:
        q.append(n)
        checked[n] = 0

ok = False
while q:
    posiq = []
    for p in q:
        update = False
        for np in graph[p]:
            if checked[np] == -1:
                checked[np] = checked[p] + 1
                update = True
                posiq.append(np)
            elif checked[np] == checked[p] + 1:
                ok = True
                break
            elif checked[np] == checked[p]:
                update = True
        if not update:
            ok = True
            break
    
    q = []
    for p in posiq:
        for np in graph[p]:
            if checked[np] == -1:
                c = 0
                for mp in graph[np]:
                    if checked[mp] == -1:
                        c += 1
                    if c >= 2: break
                if c <= 1:
                    checked[np] = checked[p] + 1
                    q.append(np)

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

Submission status: Wrong Answer

Solution code:
print("First")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

q = []
checked = [-1]*N
for n in range(N):
    if len(graph[n]) == 1:
        q.append(n)
        checked[n] = 0

ok = False
while q:
    posiq = []
    for p in q:
        update = False
        for np in graph[p]:
            if checked[np] == -1:
                checked[np] = checked[p] + 1
                update = True
                posiq.append(np)
            elif checked[np] == checked[p] + 1:
                ok = True
                break
            elif checked[np] == checked[p]:
                update = True
        if not update:
            ok = True
            break
    
    q = []
    for p in posiq:
        for np in graph[p]:
            if checked[np] == -1:
                checked[np] = checked[p] + 1
                q.append(np)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

q = []
checked = [-1]*N
for n in range(N):
    if len(graph[n]) == 1:
        q.append(n)
        checked[n] = 0

ok = False
while q:
    posiq = []
    for p in q:
        update = False
        for np in graph[p]:
            if checked[np] == -1:
                checked[np] = checked[p] + 1
                update = True
                posiq.append(np)
            elif checked[np] == checked[p] + 1:
                ok = True
                break
        if not update:
            ok = True
            break
    
    q = []
    for p in posiq:
        for np in graph[p]:
            if checked[np] == -1:
                checked[np] = checked[p] + 1
                q.append(np)

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

Submission status: Wrong Answer

Solution code:
print('First')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    d[0] = 0
    q = [0]
    q2 = deque()
    p = [None]*n
    while q:
        x = q.pop()
        for y in v[x]:
            if d[y]:
                d[y] = 0
                q.append(y)
                p[y] = x
                if len(v[y]) < 2:
                    q2.append((x,y,1))
    f = [None]*n
    c = 0
    while q2:
        x,y,k = q2.popleft()
        if k:
            if not f[x] is None and f[x] != f[y]:
                print("First")
                return
            f[x] = f[y] = c
            c += 1
        if x and f[p[x]] is None:
            q2.append((p[x],x,k^1))
    if None in f:
        print("First")
    else:
        print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    d[0] = 0
    q = [0]
    q2 = deque()
    p = [None]*n
    while q:
        x = q.pop()
        for y in v[x]:
            if d[y]:
                d[y] = 0
                q.append(y)
                p[y] = x
                if len(v[y]) < 2:
                    q2.append((x,y,1))
    f = [None]*n
    c = 0
    while q2:
        x,y,k = q2.popleft()
        if k:
            if not f[x] is None and f[x] != f[y]:
                print(f,x,y)
                print("First")
                return
            f[x] = f[y] = c
            c += 1
        if x and f[p[x]] is None:
            q2.append((p[x],x,k^1))
    if None in f:
        print("First")
    else:
        print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    d[0] = 0
    q = [0]
    q2 = deque()
    p = [None]*n
    while q:
        x = q.pop()
        for y in v[x]:
            if d[y]:
                d[y] = 0
                q.append(y)
                p[y] = x
                if len(v[y]) < 2:
                    q2.append((x,y,1))
    f = [None]*n
    while q2:
        x,y,k = q2.popleft()
        if k:
            if not f[x] is None:
                print("First")
                return
            f[x] = f[y] = 0
        if x and f[p[x]] is None:
            q2.append((p[x],x,k^1))
    if None in f:
        print("First")
    else:
        print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    d[0] = 0
    q = [0]
    q2 = []
    p = [None]*n
    while q:
        x = q.pop()
        for y in v[x]:
            if d[y]:
                d[y] = 0
                q.append(y)
                p[y] = x
                if len(v[y]) < 2:
                    q2.append((x,y,1))
    f = [None]*n
    while q2:
        x,y,k = q2.pop()
        if k:
            if not f[x] is None:
                print("First")
                return
            f[x] = f[y] = 0
        if x and f[p[x]] is None:
            q2.append((p[x],x,k^1))
    if None in f:
        print("First")
    else:
        print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque()
    d = [None]*n
    c = 0
    for i in range(n):
        if len(v[i]) < 2:
            d[i] = c
            q.append((i,0))
            c += 1
    while q:
        x,k = q.popleft()
        dx = d[x]
        for y in v[x]:
            if d[y] is None:
                if k:
                    d[y] = c
                    c += 1
                else:
                    d[y] = dx
                q.append((y,k^1))
            else:
                if d[y] != dx and not k:
                    print("First")
                    return
    print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = []
    d = [None]*n
    for i in range(n):
        if len(v[i]) < 2:
            q.append(i)
    while q:
        x = q.pop()
        for y in v[x]:
            if d[y] is None:
                if d[x] is None:
                    d[x] = d[y] = 0
                q.append(y)
    if None in d:
        print("First")
    else:
        print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    for i in range(n):
        if len(v[i]) < 2:
            break
    q = [i]
    d = [None]*n
    i = 0
    while q:
        x = q.pop()
        for y in v[x]:
            if d[y] is None:
                if d[x] is None:
                    d[x] = d[y] = i
                    i += 1
                q.append(y)
    if None in d:
        print("First")
    else:
        print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    for i in range(n):
        if len(v[i]) < 2:
            break
    q = [i]
    d = [None]*n
    d[i] = 0
    f = 1
    while q:
        x = q.pop()
        if len(v[x]) < 2 and x > i:
            f &= d[x]
            if not f:
                break
        nd = d[x]^1
        for y in v[x]:
            if d[y] is None:
                d[y] = nd
                q.append(y)
    if not f:
        print("First")
    else:
        print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        vx = v[x]
        if len(vx) == 2:
            s = [0]*2
            for i in vx:
                fi = f[i]
                if fi >= 3:
                    s[0] += 1
                    s[1] += 1
                else:
                    s[fi-1] += 1
                if s[d[x]] > 1:
                    return 1
        dpl = [0]+[f[i] for i in vx[:-1]]
        dpr = [f[i] for i in vx[1:]]+[0]
        for i in range(len(vx)-1):
            dpl[i+1] |= dpl[i]
        for i in range(len(vx)-1)[::-1]:
            dpr[i] |= dpr[i+1]
        res = 0
        for i in range(len(vx)):
            y = vx[i]
            if not check[y] and len(v[y]) > 1:
                check[y] = 1
                fx = f[x]
                fy = f[y]
                f[x] = dpl[i]|dpr[i]
                f[y] |= f[x]
                res |= dfs(y)
                f[x] = fx
                f[y] = fy
        return res
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if n == 2:
        print("Second")
        return
    for i in range(n):
        v[i].sort()
    s = [0]*n
    for i in range(n):
        if len(v[i]) <= 1:
            s[v[i][0]] += 1
    if max(s) > 1:
        print("First")
    else:
        for i in range(n):
            if len(v[i]) > 1:
                break
        d = [float("inf")]*n
        d[i] = 0
        q = [i]
        q2 = []
        f = [0]*n
        while q:
            x = q.pop()
            if len(v[x]) <= 1:
                f[x] = d[x]+1
            nd = d[x]^1
            for y in v[x]:
                if nd < d[y]:
                    d[y] = nd
                    q.append(y)
                    q2.append((x,y))
        while q2:
            x,y = q2.pop()
            f[x] |= f[y]
        check = [0]*n
        check[i] = 1
        ans = dfs(i)
        if ans:
            print("First")
        else:
            print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        vx = v[x]
        dpl = [0]+[f[i] for i in vx[:-1]]
        dpr = [f[i] for i in vx[1:]]+[0]
        for i in range(len(vx)-1):
            dpl[i+1] |= dpl[i]
        for i in range(len(vx)-1)[::-1]:
            dpr[i] |= dpr[i+1]
        if len(vx) == 2:
            s = [0]*2
            for i in vx:
                fi = f[i]
                if fi >= 3:
                    s[0] += 1
                    s[1] += 1
                else:
                    s[fi-1] += 1
                if s[d[x]] > 1:
                    return 1
                    
        res = 0
        for i in range(len(vx)):
            y = vx[i]
            if not check[y]:
                check[y] = 1
                fx = f[x]
                fy = f[y]
                f[x] = dpl[i]|dpr[i]
                f[y] |= f[x]
                res |= dfs(y)
                f[x] = fx
                f[y] = fy
        return res
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if n == 2:
        print("Second")
        return
    for i in range(n):
        v[i].sort()
    s = [0]*n
    leaf = []
    for i in range(n):
        if len(v[i]) <= 1:
            leaf.append(i)
            s[v[i][0]] += 1
    if max(s) > 1:
        print("First")
    else:
        for i in range(n):
            if len(v[i]) > 1:
                break
        d = [float("inf")]*n
        d[i] = 0
        q = [i]
        q2 = []
        f = [0]*n
        while q:
            x = q.pop()
            if len(v[x]) <= 1:
                f[x] = d[x]+1
            nd = d[x]^1
            for y in v[x]:
                if nd < d[y]:
                    d[y] = nd
                    q.append(y)
                    q2.append((x,y))
        while q2:
            x,y = q2.pop()
            f[x] |= f[y]
        check = [0]*n
        check[i] = 1
        ans = dfs(i)
        if ans:
            print("First")
        else:
            print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    s = [0]*n
    for i in range(n):
        if len(v[i]) <= 1:
            s[v[i][0]] += 1
    if max(s) > 1:
        print("First")
    else:
        print("Second")
    return

#Solve
if __name__ == "__main__":
    solve()