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

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

Solution (Python):
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()

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

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

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

Solution (Python):
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):

    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)


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

Solution (Python):
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()

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

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

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

Solution (Python):

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

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

Solution (Python):

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

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

Solution (Python):

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"
	
	
	W = [0] * N
	visit = ["No"] * N
	visit[0] = "Yes"
	Wlist = [[] for i in range(N)]
	DFS(G, W, Wlist, visit, 0)
	
	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

	
	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

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

Solution (Python):
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')

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

Solution (Python):
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)

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

Solution (Python):
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')

Solution (Python):
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')

Solution (Python):
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')

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

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

Solution (Python):
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')

Solution (Python):
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()

Solution (Python):
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())

Solution (Python):
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] = []

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