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())
arr = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

ans = 'Second'
for i in range(1, N + 1):
    if ans == 'First':
        break
    tmp = arr[i]
    cnt1 = 0
    cnt2 = 0
    for v in tmp:
        if len(arr[v]) == 1:
            cnt1 += 1
        else:
            cnt2 += 1
    if 2 <= cnt1:
        ans = 'First'
    elif cnt1 == 1 and 3 <= cnt2:
        ans = 'First'
    elif 4 <= cnt2:
        ans = 'First'

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

tree = [[] for i in range(N)]
for i in range(N - 1):
    tmp1, tmp2 = list(map(int, input().split()))
    tree[tmp1 - 1].append(tmp2 - 1)
    tree[tmp2 - 1].append(tmp1 - 1)

tree = list(filter(lambda x: len(x) == 1, tree))

new_tree = []
for ele in tree:
    new_tree.append(ele[0])

no_dup_tree = list(set(new_tree))

if len(no_dup_tree) != len(new_tree) and N != 2:
    print("First")
else:
    print("Second")

Submission status: Wrong Answer

Solution code:
N = int(input())

tree = [[] for i in range(N)]
for i in range(N - 1):
    tmp1, tmp2 = list(map(int, input().split()))
    tree[tmp1 - 1].append(tmp2 - 1)
    tree[tmp2 - 1].append(tmp1 - 1)

tree = list(filter(lambda x: len(x) == 1, tree))

new_tree = []
for ele in tree:
    new_tree.append(ele[0])

no_dup_tree = list(set(new_tree))

if len(no_dup_tree) != len(new_tree):
    print("First")
else:
    print("Second")

Submission status: Wrong Answer

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

ans = 'Second'
for i in range(1, N + 1):
    if ans == 'First':
        break
    tmp = arr[i]
    if 4 <= len(tmp):
        ans = 'First'
    cnt = 0
    for v in tmp:
        if len(arr[v]) == 1:
            cnt += 1
    if 2 <= cnt:
        ans = 'First'

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

l = [0 for i in range(N)]
ad = [[] for i in range(N)]
de1 = [0 for i in range(N)]

for i in range(N-1):
	a,b = map(int,input().split())
	l[a-1] += 1
	l[b-1] += 1
	ad[a-1].append(b-1)
	ad[b-1].append(a-1)

for i in range(N):
	if l[i] == 1:
		de1[ad[i][0]] += 1

for i in range(N):
	if de1[i] >= 2:
		print("First")
		break
else:
	print("Second")

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    if n > 10**4*9:
        return 'Third'

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                tt = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                tt = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
g=[[] for _ in xrange(n)]
cnt=[0]*n
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    cnt[a]+=1;cnt[b]+=1
    g[a].append(b)
    g[b].append(a)
par=[0]*n
for i in xrange(n):
    if cnt[i]==1:
        par[g[i][0]]+=1
for i in xrange(n):
    if par[i]>=2:
        print "First"
        exit()
print "Second"

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    t = True
    gf = collections.defaultdict(bool)
    while t:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        t = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                t = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[0]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    t = True
    gf = collections.defaultdict(bool)
    for _ in range(10):
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        t = False
        for k,v in d.items():
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                # t = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
N=int(input())
ab=[[int(i)-1 for i in input().split()] for j in range(N-1)]
ans=False

point=[[] for i in range(N)]
for piece in ab:
	point[piece[0]].append(piece[1])
	point[piece[1]].append(piece[0])

for i in range(N):
	count=0
	for piece in point[i]:
		if len(point[piece])==1:
			count+=1
	if count>1:
		ans=True

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[0]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    t = True
    gf = collections.defaultdict(bool)
    for _ in range(3):
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        t = False
        for k,v in d.items():
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                # t = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[0]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    t = True
    gf = collections.defaultdict(bool)
    while t or rf:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        t = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                # t = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[0]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    t = True
    gf = collections.defaultdict(bool)
    while t or rf:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        t = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                t = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [[] for i in range(n)]
degree = [0 for i in range(n)]

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    degree[a] += 1
    degree[b] += 1
leaf = []
for i in range(n):
    if degree[i] == 1:
        leaf.append(i)
color = ['' for i in range(n)]
while leaf:
    v = leaf.pop()
    if color[v] != '':
        continue
    p = tree[v][0]
    # print(v, p, degree, tree)
    degree[v] -= 1
    degree[p] -= 1
    tree[p].remove(v)
    if degree[p] == 1:
        leaf.append(p)

    if color[p] == 'W':
        print('First')
        exit()
    elif color[p] == 'B':
        degree[v] = 0
        continue
    color[p] = 'W'
print('Second')

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        if len(d[s] - set([m])) < 1:
            return False
        t = list(d[s] - set([m]))[0]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    t = True
    gf = collections.defaultdict(bool)
    while t:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        t = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True,-1)
                if res:
                    return 'First'
                t = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        if len(d[s] - set([m])) < 1:
            return False
        t = list(d[s] - set([m]))[0]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    t = True
    gf = collections.defaultdict(bool)
    while t:
        if rf:
            gf = collections.defaultdict(bool)
            rf = False
        t = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True,-1)
                if res:
                    return 'First'
                t = True
    return 'Second'


print(main())

Submission status: Wrong Answer

Solution code:
N = input()
E = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int, raw_input().split())
    E[a-1] += [b-1]
    E[b-1] += [a-1]
ans = False
for v in range(N):
    c = 0
    for e in E[v]:
        if len(E[e])==1:
            c += 1
    if c>=2:
        ans = True
print "First" if ans else "Second"

Submission status: Wrong Answer

Solution code:
n = input()
if n <= 3:
    print "First"
    exit(0)
g = [[] for i in xrange(n)]
for i in xrange(n-1):
    a, b = map(int, raw_input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
import sys
sys.setrecursionlimit(10**6)
chk = [1]*n
def dfs(v, prev, cnt):
    if len(g[v]) == 1 or cnt % 2 == 1:
        chk[v] = 0
    su = 0
    cnt1 = 0
    if cnt == 1:
        cnt1 += 1
    for t in g[v]:
        if t != prev:
            res = dfs(t, v, cnt+1)
            if res % 2 == 1:
                chk[v] = 0
            if res == 1:
                cnt1 += 1
            su += res
    if cnt1 >= 2:
        chk[v] = 1
    return su+1

for i in xrange(n):
    if len(g[i]) == 1:
        dfs(i, -1, 0)
        break
print "First"*any(e for e in chk) or "Second"

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n - 2))
    la = [None] * (n + 1)
    xt = [None] * (2 * n - 2)
    j = 0
    for i in xrange(n - 1):
        x = dat[j]
        y = dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 1
    c = [None] * (n + 1)
    st = [1]
    pu = st.append
    po = st.pop
    c[1] = 1
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if c[z] is None:
                c[z] = 1 - c[x]
                pu(z)
            y = xt[y]
    t = 0
    for i in xrange(1, n + 1):
        t += c[i]
    if t == n - t:
        print "Second"
    else:
        print "First"
main()

Submission status: Wrong Answer

Solution code:
N = int( input() )
adj = [ [] for i in range( N ) ]
for i in range( N - 1 ):
  u, v = map( int, input().split() )
  adj[ u - 1 ].append( v - 1 )
  adj[ v - 1 ].append( u - 1 )
cnt1 = [ sum( len( adj[ v ] ) == 1 for v in adj[ u ] ) for u in range( N ) ]
for i in range( N ):
  cnt = cnt1[ i ]
  for v in adj[ i ]:
    if len( adj[ v ] ) == 2:
      x = adj[ v ][ 0 ] + adj[ v ][ 1 ] - i
      cnt += cnt1[ x ] + 1 >= 2
  if cnt >= 2:
    exit( print( "First" ) )
print( "Second" )

Submission status: Wrong Answer

Solution code:
N = int( input() )
adj = [ [] for i in range( N ) ]
for i in range( N - 1 ):
  u, v = map( int, input().split() )
  adj[ u - 1 ].append( v - 1 )
  adj[ v - 1 ].append( u - 1 )
for i in range( N ):
  cnt = 0
  for v in adj[ i ]:
    cnt += len( adj[ v ] ) == 1
  if cnt >= 2:
    exit( print( "First" ) )
print( "Second" )

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class BipartiteGraph:
    """二部グラフの最大マッチングを求めるなどする"""
    def __init__(self, input_graph: list):
        """重み無し二部グラフinput_graphを入力する"""
        n = len(input_graph)
        self.INF = float("inf")
        self.max_bipartite_matching = -1
        
        # DFSでグラフを2色に彩色する
        visited = [-1] * n
        for i in range(n):
            if visited[i] >= 0:
                continue
            visited[i] = 0
            q = deque([i]) 
            while q:
                _from = q.pop()
                for to in input_graph[_from]:
                    if visited[to] >= 0:
                        continue
                    visited[to] = visited[_from] ^ 1
                    q.append(to)

        # 残余グラフを構築する
        self.s = n
        self.t = n + 1
        self.n = n + 2
        self.graph = [[] for i in range(self.n)]
        used = set([])
        for pos1 in range(n):
            if visited[pos1] == 0:
                self.add_edge(self.s, pos1)
            else:
                self.add_edge(pos1, self.t)
            for pos2 in input_graph[pos1]:
                if (min(pos1, pos2), max(pos1, pos2)) in used:
                    continue
                used.add((min(pos1, pos2), max(pos1, pos2)))
                if visited[pos1] == 0:
                    self.add_edge(pos1, pos2)
                else:
                    self.add_edge(pos2, pos1)
 
    def add_edge(self, _from: int, to: int):
        """残余グラフを構築
        1. _fromからtoへ向かう容量capacity = 1の辺をグラフに追加する
        2. toから_fromへ向かう容量0の辺をグラフに追加する
        """
        forward = [to, 1, None]
        forward[2] = backward = [_from, 0, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)
 
    def bfs(self, s: int, t: int):
        """capacityが正の辺のみを通ってsからtに移動可能かどうかBFSで探索
        level: sからの最短路の長さ
        """
        self.level = [-1] * self.n
        q = deque([s])
        self.level[s] = 0
        while q:
            _from = q.popleft()
            for to, capacity, _ in self.graph[_from]:
                if capacity > 0 and self.level[to] < 0:
                    self.level[to] = self.level[_from] + 1
                    q.append(to)
 
    def dfs(self, _from: int, t: int, f: int) -> int:
        """流量が増加するパスをDFSで探索
        BFSによって作られた最短路に従ってfを更新する
        """
        if _from == t:
            return f
        for edge in self.itr[_from]:
            to, capacity, reverse_edge = edge
            if capacity > 0 and self.level[_from] < self.level[to]:
                d = self.dfs(to, t, min(f, capacity))
                if d > 0:
                    edge[1] -= d
                    reverse_edge[1] += d
                    return d
        return 0
 
    def max_flow(self):
        """s-tパス上の最大流を求める = 最大マッチングを求める　= 最商店被覆を求める
        計算量: O(|E||V|^2)
        """
        if self.max_bipartite_matching >= 0:
            return self.max_bipartite_matching
        flow = 0
        while True:
            self.bfs(self.s, self.t)
            if self.level[self.t] < 0:
                break
            self.itr = list(map(iter, self.graph))
            f = self.dfs(self.s, self.t, self.INF)
            while f > 0:
                flow += f
                f = self.dfs(self.s, self.t, self.INF)
        self.max_bipartite_matching = flow
        return flow

    def maximum_matching(self):
        """最大マッチングを求める"""
        return self.max_flow()

    def minimum_point_covering(self):
        """最小点被覆を求める"""
        return self.max_flow()
      
    def maximum_independent_set(self):
        """最大安定集合を求める"""
        return (self.n - 2) - self.max_flow()

    def minimum_edge_covering(self):
        """最小辺被覆を求める"""
        return (self.n - 2) - self.max_flow()
      
      
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    
bg = BipartiteGraph(tree)
if bg.maximum_matching() * 2 == n:
    print("Second")
else:
    print("First")

Submission status: Time Limit Exceeded

Solution code:
import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf

def Fi():
    print('First')
    exit()

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

if N % 2:
    Fi()

dist = [0]*(N+1)
visited = set([1])
stack = [1]

while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf in visited:
            continue
        visited.add(vf)
        dist[vf] = not dist[vn]
        stack.append(vf)

Din = Dinic(N+2)

for i in range(1, N+1):
    if dist[i]:
        Din.addedge(0, i, 1)
        for j in Edge[i]:
            Din.addedge(i, j, 1)
    else:
        Din.addedge(i, N+1, 1)

if Din.getmf(0, N+1) != N//2:
    Fi()
print('Second')

Submission status: Time Limit Exceeded

Solution code:
N = list(map(int,input().split()))[0]
lis = [[] for i in range(N)]

for a_i,b_i in [ map(int,input().split()) for _ in range(N-1) ]:
	lis[a_i-1].append(b_i-1)
	lis[b_i-1].append(a_i-1)

flag = False
while True:
	flag = False

	sumsum = 0
	for x in lis:
		sumsum += sum(x)
	if sumsum == 0:
		print("Second")
		quit()

	for i in range(len(lis)):

		if flag:
			break

		if len(lis[i]) == 1:
			b = lis[i][0]
			lis[i].remove(b)
			lis[b].remove(i)
			for c in lis[b]:
				lis[c].remove(b)
				if len(lis[c]) == 0:
					print("First")
					quit()
			lis[b] = []
			flag = True

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
if n % 2:exit(print("First"))
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
def dfs(v, prev):
    res = sum(dfs(u, v) for u in edges[v] if u != prev)
    if res >= 2:exit(print("First"))
    return not res
print("First" if dfs(0, -float("inf")) else "Second")