Problem:


Score : 900 points

Problem Statement

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

Initially, each vertex is uncolored.

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

Select a vertex that is not painted yet.

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

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

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

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

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

Constraints

2 ≤ N ≤ 10^5

1 ≤ a_i,b_i ≤ N

a_i ≠ b_i

The input graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1 2
2 3

Sample Output 1

First

Below is a possible progress of the game:

First, Takahashi paint vertex 2 white.

Then, Aoki paint vertex 1 black.

Lastly, Takahashi paint vertex 3 white.

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

Sample Input 2

4
1 2
2 3
2 4

Sample Output 2

First

Sample Input 3

6
1 2
2 3
3 4
2 5
5 6

Sample Output 3

Second



Sample input:
3
1 2
2 3


Sample output:
First

Submission status: Wrong Answer

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

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

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

INF = float("inf")

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

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

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

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

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

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

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

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

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

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

	print(judge)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

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

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

INF = float("inf")

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

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

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

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

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

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.prev = [None] * N
		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.prev[i] = v
					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

	#BFS 偶奇判定
	BF = BFS(G, 0, N)
	odd_even = [[] for i in range(2)]
	dist = BF.dist
	for i in dist:
		if i % 2 == 0:
			odd_even[0].append(i)
		else:
			odd_even[1].append(i)

	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)
	for i in range(N):
		cnt = 0
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
		if cnt >= 2:
			judge = "First"
			break
	cnt = 0
	for i in odd_even[0]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
	if cnt >= 3:
		judge = "First"
	cnt = 0
	for i in odd_even[1]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
	if cnt >= 3:
		judge = "First"		
	#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
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
		if cnt >= 2:
			judge = "First"
			break
	cnt = 0
	for i in odd_even[0]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
	if cnt >= 3:
		judge = "First"
	cnt = 0
	for i in odd_even[1]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
	if cnt >= 3:
		judge = "First"

	#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
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
		if cnt >= 2:
			judge = "First"
			break
	cnt = 0
	for i in odd_even[0]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
	if cnt >= 3:
		judge = "First"
	cnt = 0
	for i in odd_even[1]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
	if cnt >= 3:
		judge = "First"

	print(judge)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

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

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

INF = float("inf")

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

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

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

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

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

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.prev = [None] * N
		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.prev[i] = v
					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

	#BFS 偶奇判定
	BF = BFS(G, 0, N)
	odd_even = [[] for i in range(2)]
	dist = BF.dist
	for i in dist:
		if i % 2 == 0:
			odd_even[0].append(i)
		else:
			odd_even[1].append(i)

	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)
	for i in range(N):
		cnt = 0
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
		if cnt >= 2:
			judge = "First"
			break
	cnt = 0
	for i in odd_even[0]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
	cnt = 0
	for i in odd_even[1]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
			
	#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
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
		if cnt >= 2:
			judge = "First"
			break
	cnt = 0
	for i in odd_even[0]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"
	cnt = 0
	for i in odd_even[1]:
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
	if cnt >= 2 and N % 2 == 1:
		judge = "First"

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

	print(judge)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

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

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

INF = float("inf")

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

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

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

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

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

#処理内容
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 判定
	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
		for j in Wlist[i]:
			if j == 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)
	# print(Wlist)
	for i in range(N):
		cnt = 0
		for j in Wlist[i]:
			if j == 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)
	# print(Wlist)
	for i in range(N):
		cnt = 0
		for j in Wlist[i]:
			if j == 1:
				cnt += 1
		if cnt >= 2:
			judge = "First"
			break

	print(judge)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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 = [[] for _ in range(N+1)]
while que:
    v = que.popleft()
    for u in adj[v]:
        if seen[u] == 0:
            seen[u] = 1
            par[u] = v
            child[v].append(u)
            que.append(u)

seq = deque()
for i in range(1, N+1):
    if len(child[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
    if seen[par[par[c]]] != 0:
        seq.append(par[par[c]])

print('Second')

Submission status: Wrong Answer

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:
			return 1

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

Submission status: Wrong Answer

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()
		else:
			return 0

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

Submission status: Wrong Answer

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

	def dfs(x, rt):
		l = []
		cnt = 0
		arb = False
		for v in adj[x]:
			if v == rt:
				continue
			else:
				l.append(dfs(v, x))
				if l[-1] == 1:
					cnt += 1
				elif l[-1] == 2:
					arb = True
		if not l:
			return 1
		elif len(l) == 1:
			if l[0] == 2:
				return 2
			else:
				return 1^l[0]
		elif cnt != 1 or arb:
			print("First")
			sys.exit()
		else:
			return 2

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

Submission status: Wrong Answer

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

	def dfs(x, rt):
		l = []
		cnt = 0
		arb = False
		for v in adj[x]:
			if v == rt:
				continue
			else:
				l.append(dfs(v, x))
				if l[-1] == 1:
					cnt += 1
				elif l[-1] == 2:
					arb = True
		if not l:
			return 1
		elif len(l) == 1:
			return 1^l[0]
		elif cnt != 1 or arb:
			print("First")
			sys.exit()
		else:
			return 2

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

n = int(input())
deg = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
odd_branch = [0 for _ in range(n)]
even_branch = [0 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:
	visited = [False for _ in range(n)]
	cnt = 0
	next_origin = set()
	def dfs(x, bl):
		global cnt, next_origin
		if deg[x] > 2 and visited[x] == False:
			odd_branch[x] += bl
			next_origin.add(x)
			even_branch[x] += (1^bl)
			return
		else:
			#print(x)
			visited[x] = True
			cnt += 1
			for c in adj[x]:
				if visited[c] == False:
					#visited[c] = True
					#cnt += 1
					dfs(c, 1^bl)
		return

	for i in range(n):
		if deg[i] == 1:
			visited[i] = True
			#cnt += 1
			dfs(i, 0)

	#print(cnt, next_origin)
	while cnt + len(next_origin) < n:
		li = list(next_origin)
		next_origin = set()
		for o in li:
			visited[o] = True
			#cnt += 1
			dfs(o, 1^(odd_branch[o]%2))
		
	for i in range(n):
		if deg[i] > 2 and (odd_branch[i] > 1 or even_branch[i] == deg[i]):
			print("First")
			break
	else:
		print("Second")

Submission status: Wrong Answer

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

n = int(input())
deg = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
odd_branch = [0 for _ in range(n)]
even_branch = [0 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:
	visited = [False for _ in range(n)]
	cnt = 0
	next_origin = set()
	def dfs(x, bl):
		global cnt, next_origin
		if deg[x] > 2 and visited[x] == False:
			odd_branch[x] += bl
			next_origin.add(x)
			even_branch[x] += (1^bl)
			return
		else:
			#print(x)
			visited[x] = True
			cnt += 1
			for c in adj[x]:
				if visited[c] == False:
					#visited[c] = True
					#cnt += 1
					dfs(c, 1^bl)
		return

	for i in range(n):
		if deg[i] == 1:
			visited[i] = True
			#cnt += 1
			dfs(i, 0)

	#print(cnt, next_origin)
	while cnt + len(next_origin) < n:
		li = list(next_origin)
		next_origin = set()
		for o in li:
			visited[o] = True
			#cnt += 1
			dfs(o, odd_branch[o]%2)
		
	for i in range(n):
		if deg[i] > 2 and (odd_branch[i] > 1 or even_branch[i] == deg[i]):
			print("First")
			break
	else:
		print("Second")

Submission status: Wrong Answer

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

n = int(input())
deg = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
odd_branch = [0 for _ in range(n)]
#even_branch = [0 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:
	visited = [False for _ in range(n)]
	cnt = 0
	next_origin = set()
	def dfs(x, bl):
		global cnt, next_origin
		if deg[x] > 2 and visited[x] == False:
			odd_branch[x] += bl
			next_origin.add(x)
			#even_branch[x] += (1^bl)
			return
		else:
			#print(x)
			visited[x] = True
			cnt += 1
			for c in adj[x]:
				if visited[c] == False:
					#visited[c] = True
					#cnt += 1
					dfs(c, 1^bl)
		return

	for i in range(n):
		if deg[i] == 1:
			visited[i] = True
			#cnt += 1
			dfs(i, 0)

	#print(cnt, next_origin)
	while cnt + len(next_origin) < n:
		li = list(next_origin)
		next_origin = set()
		for o in li:
			visited[o] = True
			#cnt += 1
			dfs(o, 1^odd_branch[o])
		
	for i in range(n):
		if deg[i] > 2 and odd_branch[i] != 1:
			print("First")
			break
	else:
		print("Second")

Submission status: Wrong Answer

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

n = int(input())
deg = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
odd_branch = [0 for _ in range(n)]
#even_branch = [0 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:
	visited = [False for _ in range(n)]
	cnt = 0
	next_origin = set()
	def dfs(x, bl):
		global cnt, next_origin
		if deg[x] > 2 and visited[x] == False:
			odd_branch[x] += bl
			next_origin.add(x)
			#even_branch[x] += (1^bl)
			return
		else:
			#print(x)
			visited[x] = True
			cnt += 1
			for c in adj[x]:
				if visited[c] == False:
					#visited[c] = True
					#cnt += 1
					dfs(c, 1^bl)
		return

	for i in range(n):
		if deg[i] == 1:
			visited[i] = True
			#cnt += 1
			dfs(i, 0)

	#print(cnt, next_origin)
	while cnt + len(next_origin) < n:
		li = list(next_origin)
		next_origin = set()
		for o in li:
			visited[o] = True
			#cnt += 1
			dfs(o, odd_branch[o])
		
	for i in range(n):
		if deg[i] > 2 and odd_branch[i] != 1:
			print("First")
			break
	else:
		print("Second")

Submission status: Wrong Answer

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

n = int(input())
deg = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
odd_branch = [0 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:
	def dfs(x, pr, bl):
		if deg[x] > 2:
			odd_branch[x] += bl
			return
		else:
			for c in adj[x]:
				if c == pr:
					continue
				else:
					dfs(c, x, 1^bl)
		return

	for i in range(n):
		if deg[i] == 1:
			dfs(i, -1, 0)

	for i in range(n):
		if deg[i] > 2 and odd_branch[i] != 1:
			print("First")
			break
	else:
		print("Second")

Submission status: Wrong Answer

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

n = int(input())
deg = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
odd_branch = [0 for _ in range(n)]
even_branch = [0 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:
	def dfs(x, pr, bl):
		if deg[x] > 2:
			odd_branch[x] += bl
			even_branch[x] += (1^bl)
			return
		else:
			for c in adj[x]:
				if c == pr:
					continue
				else:
					dfs(c, x, 1^bl)
		return

	for i in range(n):
		if deg[i] == 1:
			dfs(i, -1, 0)

	if max(odd_branch) > 1:
		print("First")
	else:
		for i in range(n):
			if even_branch[i] == deg[i]:
				print("First")
				break
		else:
			print("Second")

Submission status: Wrong Answer

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

n = int(input())
deg = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
odd_branch = [0 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:
	def dfs(x, pr, bl):
		if deg[x] > 2:
			odd_branch[x] += bl
			return
		else:
			for c in adj[x]:
				if c == pr:
					continue
				else:
					dfs(c, x, 1^bl)
		return

	for i in range(n):
		if deg[i] == 1:
			dfs(i, -1, 0)

	if max(odd_branch) > 1:
		print("First")
	else:
		print("Second")

Submission status: Wrong Answer

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

N = int(input())
dim = [0]*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] == 1]
used = set(L)
stack = L[:]
while stack:
    vn = stack.pop()
    if not vn:
        Fi()
    pv = par[vn]
    if pv in used:
        Fi()
    used.add(pv)
    if not pv:
        continue
    ppv = par[pv]
    dim[pv] -= 2
    dim[ppv] -= 1
    if (ppv and dim[ppv] == 1) or (not ppv and dim[ppv] == 0):
        stack.append(ppv)
print('Second')

Submission status: Wrong Answer

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

N = int(input())
dim = [0]*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] == 1]
used = set(L)
stack = L[:]
while stack:
    vn = stack.pop()
    if not vn:
        Fi()
    pv = par[vn]
    if pv in used:
        Fi()
    used.add(pv)
    if not pv:
        continue
    ppv = par[pv]
    dim[pv] -= 1
    dim[ppv] -= 1
    if (ppv and dim[ppv] == 1) or (not ppv and dim[ppv] == 0):
        stack.append(ppv)
print('Second')

Submission status: Wrong Answer

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

N = int(input())
dim = [0]*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] == 1]
used = set(L)
stack = L[:]
while stack:
    vn = stack.pop()
    if not vn:
        Fi()
    pv = par[vn]
    if pv in used:
        Fi()
    used.add(pv)
    if not pv:
        continue
    ppv = par[pv]
    dim[pv] -= 1
    dim[ppv] -= 1
    if dim[ppv] == 1 or (not ppv and dim[ppv] == 0):
        stack.append(ppv)
print('Second')

Submission status: Wrong Answer

Solution code:
from sys import exit
def Fi():
    print('First')
    exit()
N = int(input())
dim = [0]*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)
l = dim.index(1)
stack = [l]
col = [-1]*N
col[l] = 0
visited = set([l])
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf in visited:
            continue
        visited.add(vf)
        col[vf] = 1 - col[vn]
        stack.append(vf)
if col.count(0) != col.count(1):
    Fi()
print('Second')

Submission status: Wrong Answer

Solution code:
from sys import exit
def Fi():
    print('First')
    exit()
N = int(input())
dim = [0]*N
Edge = [[] for _ in range(N)]
D = [0]*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)
l = dim.index(1)
stack = [l]
col = [-1]*N
col[l] = 0
visited = set([l])
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if dim[vf] == 1:
            D[vn] += 1
        if vf in visited:
            continue
        visited.add(vf)
        col[vf] = 1 - col[vn]
        stack.append(vf)
if (all([c == 0 for c, d in zip(col, dim) if d == 1]) and any([c == 0 for c, d in zip(col, dim) if d != 1])) or any([b > 1 for b in D]):
    Fi()
print('Second')

Submission status: Wrong Answer

Solution code:
from sys import exit
def Fi():
    print('First')
    exit()
N = int(input())
dim = [0]*N
Edge = [[] for _ in range(N)]
D = [0]*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)
l = dim.index(1)
stack = [l]
col = [-1]*N
col[l] = 0
visited = set([l])
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if dim[vf] == 1:
            D[vn] += 1
        if vf in visited:
            continue
        visited.add(vf)
        col[vf] = 1 - col[vn]
        stack.append(vf)
if all([c == 0 for c, d in zip(col, dim) if d == 1]) or any([b > 1 for b in D]):
    Fi()
print('Second')

Submission status: Wrong Answer

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]
match=[-1]*(n)
used=[0]*(n)
res=0
def dfs(x):
	used[x]=True
	for u in g[x]:
		w=match[u]
		if w<0 or (not used[x] and dfs(w)):
			match[u]=x
			match[x]=u
			return True
	return False
for i in range(n):
	if match[i]<0:
		used=[0]*(n)
		res+=dfs(i)
print("Second" if res==int(n/2) else "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):
    tmp = arr[i]
    cnt = 0
    for v in tmp:
        if len(arr[v]) == 1:
            cnt += 1
    if 2 <= cnt:
        ans = 'First'
        break
print(ans)

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 2 <= cnt2:
        ans = 'First'

print(ans)

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 3 <= cnt2:
        ans = 'First'

print(ans)