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: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    only = []
    sign = [False]*n
    for i in range(n):
        if len(g[i]) == 1:
            only.append(i)
    while only:
        i = only.pop()
        if not g[i]:
            print("Second")
            return
        j = g[i].pop()
        g[j].remove(i)
        if sign[i] and not g[j]:
            print("First")
            return
        if not sign[i] and sign[j]:
            print("First")
            return
        if not sign[j] and not sign[i]:
            sign[j] = True
        if len(g[j]) == 1:
            only.append(j)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in G[v]:
        if memo[u]:
            continue
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1:
            matched[u] = v
            return True
        elif dfs(matched[u], visited) == 1:
            matched[u] = v
            return True
        else:
            memo[u] = 1
    return False

cnt = 0
matched = [-1] * n
visited = set()
memo = [0] * n
for i in range(n):
    cnt += int(dfs(i, set()))

if cnt == n:
    print("Second")
else:
    print("First")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in G[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            matched[v] = u
            return True
    return False

cnt = 0
matched = [-1] * n
for i in range(n):
    if matched[i] != -1:
        continue
    cnt += int(dfs(i, set())) * 2

if cnt == n:
    print("Second")
else:
    print("First")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in G[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False

cnt = 0
matched = [-1] * n
for i in range(n):
    cnt += int(dfs(i, set()))

if cnt == n:
    print("Second")
else:
    print("First")

Submission status: Accepted

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 examD():
    def dfs(v, edges, n, visited, matched):
        for u in edges[v]:
            if u in visited:
                continue
            visited.add(u)
            if matched[u] == -1 or dfs(matched[u], edges, n, visited, matched):
                matched[u] = v
                return True
        return False
    N = I()
    V = [set()for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].add(b)
        V[b].add(a)
    cnt = 0
    matched = [-1] * N
    for s in range(N):
        cnt += dfs(s, V, N, set(), matched)
    #print(cnt)
    if cnt<N:
        print("First")
    else:
        print("Second")
    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: Accepted

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    only = []
    sign = [False]*n
    for i in range(n):
        if len(g[i]) == 1:
            only.append(i)
    while only:
        i = only.pop()
        if not g[i]:
            print("Second")
            return
        j = g[i].pop()
        g[j].remove(i)
        if sign[i] and not g[j]:
            print("First")
            return
        if not sign[i] and sign[j]:
            print("First")
            return
        if not sign[j] and not sign[i]:
            sign[j] = True
        if len(g[j]) == 1:
            only.append(j)


main()

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
E=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  E[a].append(b)
  E[b].append(a)
D=deque([0])
V=[0]*n
V[0]=1
A=[0]
P=[-1]*n
while len(D)>0:
  x=D[0]
  D.popleft()
  for c in E[x]:
    if V[c]==0:
      D.append(c)
      A.append(c)
      P[c]=x
      V[c]=1
A=A[::-1]
VV=[0]*n
f=0
for c in A:
  if VV[c]==0:
    if P[c]==-1 or VV[P[c]]==1:
      f=1
    else:
      VV[c]=1
      VV[P[c]]=1
if f==1:
  print("First")
else:
  print("Second")

Submission status: Accepted

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 = set()
    for p in posiq:
        for np in graph[p]:
            if checked[np] == -1 and not np in q:
                c = 0
                for mp in graph[np]:
                    if checked[mp] == -1:
                        c += 1
                    if c >= 2: break
                if c <= 1:
                    q.add(np)
    for np in q:
        checked[np] = checked[p] + 1

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

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

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

ans=[0 for i in range(N)]
subtreesize=[0 for i in range(N)]

def dfs(v,pv):
    if edge[v]==[pv]:
        subtreesize[v]=1
        ans[v]+=((N-1)%2==1)
        return subtreesize[v]

    a=0
    size=1
    for nv in edge[v]:
        if nv==pv:
            continue
        else:
            size+=dfs(nv,v)
            a+=(subtreesize[nv]%2==1)

    rest=N-size
    a+=(rest%2==1)
    ans[v]=a
    subtreesize[v]=size
    return size

dfs(0,-1)
check=[1]*N
if check==ans:
    print("Second")
else:
    print("First")

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc014/tasks/agc014_d

白にしか隣接しない白を作れれば勝ちである
黒は、直前に置かれた白に対して対策するような動きをする羽目になる

距離2の葉の対があったら100%可能

ある時点での残りの森を考える(残りのどの点も黒が隣接していないとする)
葉に白を置く→葉において阻止
葉に隣接する点にしろを置く→葉において阻止
それ以外の点は、置いたら横に置くだけ(葉ではないので、隣接頂点が存在する)

なので、十分性もおｋ？
距離2の葉が存在するかだけを判定すればよさそう

そうでないとき、
奇数個の頂点の部分木が2つ以上存在したらおｋ？
検証してみるか

"""

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

import sys
sys.setrecursionlimit(500000)

if N == 2:
    print ("Second")
    sys.exit()

def dfs(v,p):

    if len(lis[v]) == 1:
        return 1,1

    pl = 0
    cnum = 0
    oddc = 0
    for nex in lis[v]:
        if nex != p:
            lf,nc = dfs(nex,v)
            pl += lf
            cnum += nc
            oddc += nc % 2

    if (N-(cnum+1)) % 2 == 1:
        oddc += 1

    if pl >= 2 or oddc >= 2:
        print ("First")
        sys.exit()

    return 0,cnum+1


fi = None
for i in range(N):
    if len(lis[i]) > 1:
        fi = i
        break

dfs(fi,fi)
print ("Second")

Submission status: Accepted

Solution code:
from collections import deque


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)
    
root = 0
par = {root: -1}
q = deque([root])
topo = []
while q:
    v = q.popleft()
    topo.append(v)
    for nxt_v in tree[v]:
        if nxt_v in par:
            continue
        par[nxt_v] = v
        q.append(nxt_v)

used = [False] * n
for v in topo[::-1]:
    if used[v]:
        continue
    else:
        used[v] = True
        if par[v] == -1:
            print("First")
            exit()
        if used[par[v]]:
            print("First")
            exit()
        used[par[v]] = True
print("Second")

Submission status: Accepted

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
if n == 2:
  print("Second")
  exit()
stack = []
root = 0
for i in range(1,n+1)[::-1]:
  if deg[i] == 1:
    stack.append(i)
  else:
    root = i
flg = 0
deg[root] += 1
dp = [[] for i in range(n+1)]
dist = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    if dp[x].count(0)>=2:
      flg = 1
    if dp[x].count(0):
      dist[x] = 1
    else:
      dist[x] = 0
  else:
    dist[x] = 0
  for y in graph[x]:
    if deg[y] >= 2:
      dp[y].append(dist[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg or dist[root]==0:
  print("First")
else:
  print("Second")

Submission status: Accepted

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

def main():
    N = int(input())
    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)

    Q = [0]
    P = [-1] * N
    R = []
    while Q:
        i = Q.pop()
        R.append(i)
        for j in X[i]:
            P[j] = i
            X[j].remove(i)
            Q.append(j)
    
    node_type = [0] * N # 1: Leaf etc. 2: Node with a leaf child
    for i in R[::-1]:
        t = sum([1 if node_type[j] == 1 else 0 for j in X[i]])
        if t > 1:
            return 1
        if t:
            node_type[i] = 2
        
        t = sum([1 if node_type[j] <= 1 else 0 for j in X[i]])
        if t == 0:
            node_type[i] = 1
    
    return 1 if node_type[0] == 1 else 0

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

Submission status: Accepted

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):
		cnt = 0
		jud = "Yes"
		for j in Wlist[i]:
			if j % 2 == 1:
				cnt += 1
		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 % 2 == 1:
				cnt += 1
		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 % 2 == 1:
				cnt += 1
		if cnt >= 2:
			judge = "First"
			break

	if N % 2 == 1:
		judge = "First"

	print(judge)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.buffer.readline

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

que = deque()
que.append(1)
seen = [0] * (N+1)
seen[1] = 1
par = [0] * (N+1)
child_num = [0] * (N+1)
while que:
    v = que.popleft()
    for u in adj[v]:
        if seen[u] == 0:
            seen[u] = 1
            par[u] = v
            child_num[v] += 1
            que.append(u)

seq = deque()
for i in range(1, N+1):
    if child_num[i] == 0:
        seq.append(i)

while seq:
    c = seq.pop()
    seen[c] = 0
    if seen[par[c]] == 0:
        print('First')
        exit()
    seen[par[c]] = 0
    child_num[par[par[c]]] -= 1
    if child_num[par[par[c]]] == 0:
        seq.append(par[par[c]])

print('Second')

Submission status: Accepted

Solution code:
N = int(input())

if N%2==1:
    print("First")
    exit()
elif N==2:
    print("Second")
    exit()

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

E_dim = [len(e) for e in E]
E_set = [set(e) for e in E]
q = []
for v, (dim, e) in enumerate(zip(E_dim, E)):
    if dim==1:
        for u in e:
            if E_dim[u] == 2:
                q.append(v)
                
while q:
    v = q.pop()
    u = E_set[v].pop()
    if E_dim[u] == 1:
        print("Second")
        exit()
    E_set[u].remove(v)
    w = E_set[u].pop()
    E_set[w].remove(u)
    E_dim[w] -= 1
    if E_dim[w] == 1:
        x = E_set[w].copy().pop()
        if E_dim[x] == 2:
            q.append(w)
    elif E_dim[w] == 2:
        for x in E_set[w]:
            if E_dim[x] == 1:
                q.append(x)
print("First")

Submission status: Accepted

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

"""
次数1のところにちょっかいを出すことを繰り返す。ダブルリーチが実現できたら勝ち。
"""

N = int(input())
AB = [tuple(int(x)-1 for x in row.split()) for row in sys.stdin.readlines()]

graph = [set() for _ in range(N)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)

deg = [len(x) for x in graph]
deg_1 = set(i for i,x in enumerate(deg) if x == 1)

bl = False
while deg_1:
    x = deg_1.pop()
    y = graph[x].pop()
    graph[y].remove(x)
    for z in graph[y]:
        if z == x:
            continue
        graph[z].remove(y)
        if deg[z] == 1:
            bl = True
            break
        deg[z] -= 1
        if deg[z] == 1:
            deg_1.add(z)
    if bl:break
    graph[y].clear()
    if y in deg_1:
        deg_1.remove(y)

answer = 'First' if bl else 'Second'
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
deg = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
	deg[a-1] += 1
	deg[b-1] += 1

M = max(deg)
if M == 1:
	print("Second")
elif M == 2:
	if n%2 == 1:
		print("First")
	else:
		print("Second")
else:
	for i in range(n):
		if deg[i] > 2:
			ori = i
			break

	l = [[] for _ in range(n)]
	def dfs(x, rt):
		cnt = 0
		for v in adj[x]:
			if v == rt:
				continue
			else:
				l[x].append(dfs(v, x))
				if l[x][-1] == 1:
					cnt += 1
		if not l[x]:
			return 1
		elif len(l[x]) == 1:
			return 1^l[x][0]
		elif cnt > 1:
			print("First")
			sys.exit()
		elif cnt == 1:
			return 0
		else:
			if x == ori:
				print("First")
				sys.exit()
			return 1

	dfs(ori, -1)
	print("Second")

Submission status: Accepted

Solution code:
from sys import exit
def Fi():
    print('First')
    exit()

N = int(input())
dim = [-1]*N
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    dim[a-1] += 1
    dim[b-1] += 1
    Edge[a-1].append(b-1)
    Edge[b-1].append(a-1)
par = [None] + [0]*(N-1)
stack = [0]
visited = set([0])
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf in visited:
            continue
        visited.add(vf)
        par[vf] = vn
        stack.append(vf)

L = [i for i in range(1,N) if dim[i] == 0]
used = set(L)
stack = L[:]
mat = [0]*N
dim[0] += 2
while stack:
    vn = stack.pop()
    pv = par[vn]
    if pv is None:
        break
    if mat[vn] == 0:
        mat[vn] += 1
        mat[pv] += 1
    dim[pv] -= 1
    if dim[pv] == 0:
        stack.append(pv)
print('Second' if all(m == 1 for m in mat) else 'First')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
Edges=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    Edges[a].append(b)
    Edges[b].append(a)
while sum([len(Edges[i]) for i in range(n)]):
    for i in range(n):
        if len(Edges[i])==1:
            j=Edges[i][0]
            Edges[i].remove(j)
            Edges[j].remove(i)
            for k in Edges[j]:
                Edges[k].remove(j)
                if not Edges[k]:
                    print('First')
                    exit()
            Edges[j]=[]
print('Second')

Submission status: Accepted

Solution code:
n=int(input())
g=[[] for i in range(n+1)]
for i in range(n-1):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
def dfs(x,p):
	s=sum([dfs(u,x) for u in g[x] if u!=p])
	return s^1 if s<2 else 2
print("First" if dfs(1,1) else "Second")

Submission status: Accepted

Solution code:
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
	u,v=map(lambda x:int(x)-1,input().split())
	g[u]+=[v]
	g[v]+=[u]
while sum([len(g[i]) for i in range(n)])>0:
	for i in range(n):
		if len(g[i])==1:
			u=g[i][0]
			g[i].remove(u)
			g[u].remove(i)
			for v in g[u]:
				g[v].remove(u)
				if len(g[v])==0:
					print("First")
					exit()
			g[u]=[]
print("Second")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)


def dfs(v, p):
    result = sum(dfs(c, v) for c in edges[v] if c != p)
    if result >= 2:
        print('First')
        exit()
    return not result


n = int(input())
if n % 2:
    print('First')
    exit()

edges = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].add(b)
    edges[b].add(a)

print('First' if dfs(0, None) else 'Second')

Submission status: Accepted

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)
    par = [0] * (n + 1)
    st = [1]
    pu = st.append
    po = st.pop
    f = 1
    c[0] = 0
    while st:
        x = po()
        if c[x] is None:
            c[x] = -1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if c[z] is None:
                    par[z] = x
                    pu(z)
                y = xt[y]
        else:
            if c[x] == -1:
                if c[par[x]] == 0:
                    print "First"
                    return
                c[par[x]] = 0
                f = 0
            c[x] = 0
    print "Second"
main()

Submission status: Accepted

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)
    kk = None
    for _ in range(n-1):
        a,b = LI()
        kk = [a,b]
        d[a].add(b)
        d[b].add(a)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                vt = list(v)[0]
                if len(d[vt]) == 1:
                    continue
                for vv in d[vt]:
                    if vv == k:
                        continue
                    if vt in d[vv]:
                        d[vv].remove(vt)
                d[vt] = set([k])
                tt = True
            elif len(v) == 0:
                return 'First'
    return 'Second'


print(main())

Submission status: Accepted

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)

while True:

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

	for i in range(len(lis)):

		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] = []

Submission status: Accepted

Solution code:
n = input()
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)
used = {}
flag = [[0]*2 for i in xrange(n)]
def dfs(v, prev):
    if (v, prev) in used:
        return used[v, prev]
    su = 1
    for t in g[v]:
        if t != prev:
            su += dfs(t, v)
    used[v, prev] = su
    return su

for i in xrange(n):
    dfs(i, -1)
for v in xrange(n):
    cnt_o = 0
    for t in g[v]:
        if used[t, v] % 2 == 1:
            cnt_o += 1
    if cnt_o > 1:
        print "First"
        break
else:
    print "Second"

Submission status: Accepted

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)]

first = False
while leaf:
    v = leaf.pop()
    if degree[v] == 0:
        first = True
        continue
    degree[v] = 0
    p = tree[v][0]
    # tree[p].remove(v)
    # degree[p] -= 1
    color[v] = 'B'
    color[p] = 'W'
    for np in tree[p]:
        tree[np].remove(p)
        degree[np] -= 1
        if degree[np] == 0:
            first = True
        elif degree[np] == 1:
            leaf.append(np)

for i in range(n):
    if color[i] == '' and degree[i] == 0:
        first = True

print('First' if first else 'Second')