Problem:


Score : 400 points

Problem Statement

Fennec and Snuke are playing a board game.

On the board, there are N cells numbered 1 through N, and N-1 roads, each connecting two cells. Cell a_i is adjacent to Cell b_i through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.

Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored.
Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell.
More specifically, each player performs the following action in her/his turn:

Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.

Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.

A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.

Constraints

2 \leq N \leq 10^5

1 \leq a_i, b_i \leq N

The given 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

If Fennec wins, print Fennec; if Snuke wins, print Snuke.

Sample Input 1

7
3 6
1 2
3 1
7 4
5 7
1 4

Sample Output 1

Fennec

For example, if Fennec first paints Cell 2 black, she will win regardless of Snuke's moves.

Sample Input 2

4
1 4
4 2
2 3

Sample Output 2

Snuke



Sample input:
7
3 6
1 2
3 1
7 4
5 7
1 4


Sample output:
Fennec

Submission status: Runtime Error

Solution code:
def sp(road,used,node,goal,path):
    if node == goal:
        return True
    for x in road[node]:
        if used[x]!=1:
            used[x]=1
            if sp(road,used,x,goal,path):
                used[x]=2
                path.append(x)
                return True

def dps(road,used,node):
    for x in road[node]:
        if used[x]!=2:
            used[x]=2
            return dps(road,used,x)+1
    return 0
    
N=int(input())
road=[[] for _ in range(N)]
used=[0 for _ in range(N)]

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

path=[]
sp(road,used,0,N-1,path)

mid=len(path)//2+len(path)%2

f=[0]+path[:mid]
s=[N-1]+path[mid:]

black=mid
for x in f:
    black+=dps(road,used,x)
white=len(path)-mid
for x in s:
    white+=dps(road,used,x)

if black>white:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
road=[[] for _ in range(N)]
used=[0 for _ in range(N)]

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

start=0
for i in range(N):
    if len(road[i])==1:
        start=i
        break
used[start]=1

f=0
s=0
for i in range(N):
    if start == 0:
        f=i
    elif start ==N-1:
        s=i
    for x in road[start]:
        if used[x]!=1:
            start=x

mid=(N-1)/2
if abs(mid-f)<abs(mid-s):
    print('Fennec')
elif abs(mid-f)>abs(mid-s):
    print('Snuke')
else:
    if N%2==0:
        print('Snuke')
    else:
        print('Fennec')

Submission status: Runtime Error

Solution code:
import math,sys


sys.setrecursionlimit(1500)
 
def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 
 
 
N = int(input())
 
# Y,P,i
adj = {}
 
for i in range(N):
	adj[i] = []
 
 
for i in range(N-1):
	a, b = list(map(int, input().split(' ')))
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
 
length_from_1 = [0]*N
length_from_N = [0]*N
 
def dfs(s, d, visited, d_list):
 
	d_list[s] = d
	visited.add(s)
 
	for next_node in adj[s]:
		if(next_node not in visited):
			dfs(next_node, d+1, visited, d_list)
 
dfs(0, 0, set([]), length_from_1)
dfs(N-1, 0, set([]), length_from_N)
 
# [0, 1, 1, 1, 3, 2, 2]
# [2, 3, 3, 1, 1, 4, 0]
 
snuke = 0
fennec = 0
for i in range(N):
	if(length_from_1[i] <= length_from_N[i]):
		fennec +=1
	else:
		snuke +=1
 
if(fennec>snuke):
	print("Fennec")
else:
	print("Snuke")

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(1500)
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)



N = int(input())

# Y,P,i
adj = {}

for i in range(N):
	adj[i] = []


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

length_from_1 = [0]*N
length_from_N = [0]*N

def dfs(s, d, visited, d_list):

	d_list[s] = d
	visited.add(s)

	for next_node in adj[s]:
		if(next_node not in visited):
			dfs(next_node, d+1, visited, d_list)

dfs(0, 0, set([]), length_from_1)
dfs(N-1, 0, set([]), length_from_N)

# [0, 1, 1, 1, 3, 2, 2]
# [2, 3, 3, 1, 1, 4, 0]

snuke = 0
fennec = 0
for i in range(N):
	if(length_from_1[i] <= length_from_N[i]):
		fennec +=1
	else:
		snuke +=1

if(fennec>snuke):
	print("Fennec")
else:
	print("Snuke")

Submission status: Runtime Error

Solution code:
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)



N = int(input())

# Y,P,i
adj = {}

for i in range(N):
	adj[i] = []


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

length_from_1 = [0]*N
length_from_N = [0]*N

def dfs(s, d, visited, d_list):

	d_list[s] = d
	visited.add(s)

	for next_node in adj[s]:
		if(next_node not in visited):
			dfs(next_node, d+1, visited, d_list)

dfs(0, 0, set([]), length_from_1)
dfs(N-1, 0, set([]), length_from_N)

# [0, 1, 1, 1, 3, 2, 2]
# [2, 3, 3, 1, 1, 4, 0]

snuke = 0
fennec = 0
for i in range(N):
	if(length_from_1[i] <= length_from_N[i]):
		fennec +=1
	else:
		snuke +=1

if(fennec>snuke):
	print("Fennec")
else:
	print("Snuke")

Submission status: Runtime Error

Solution code:
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)



N = int(input())

# Y,P,i
adj = {}

for i in range(N):
	adj[i] = []


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

length_from_1 = [0]*N
length_from_N = [0]*N

def dfs(s, d, visited, d_list):

	d_list[s] = d
	visited.add(s)

	for next_node in adj[s]:
		if(next_node not in visited):
			dfs(next_node, d+1, visited, d_list)

dfs(0, 0, set([]), length_from_1)
dfs(N-1, 0, set([]), length_from_N)

# [0, 1, 1, 1, 3, 2, 2]
# [2, 3, 3, 1, 1, 4, 0]

snuke = 0
fennec = 0
for i in range(N):
	if(length_from_1[i] <= length_from_N[i]):
		fennec +=1
	else:
		snuke +=1

if(fennec>snuke):
	print("Fennec")
else:
	print("Snuke")

Submission status: Runtime Error

Solution code:
# ABC 067 D
import sys
sys.setrecursionlimit(100000)

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

kyori1 = [100000 for k in range(N+1)]
kyori2 = [100000 for k in range(N+1)]

def dfs1(now, dist):
    for tsugi in G[now]:
        if kyori1[tsugi] == 100000:
            kyori1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

def dfs2(now, dist):
    for tsugi in G[now]:
        if kyori2[tsugi] == 100000:
            kyori2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

kyori1[1] = 0
dfs1(1,0)

kyori2[N] = 0
dfs2(N,0)

s = 0
f = 0
for k in range(1,N+1):
    if kyori1[k] <= kyori2[k]:
        f += 1
    else:
        s += 1

print("Fennec" if f > s else "Snuke")

Submission status: Runtime Error

Solution code:
# ABC 067 D
N = int(input())
G = [[] for k in range(N+1)]
for k in range(N-1):
    a, b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)

kyori1 = [100000 for k in range(N+1)]
kyori2 = [100000 for k in range(N+1)]

def dfs1(now, dist):
    for tsugi in G[now]:
        if kyori1[tsugi] == 100000:
            kyori1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

def dfs2(now, dist):
    for tsugi in G[now]:
        if kyori2[tsugi] == 100000:
            kyori2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

kyori1[1] = 0
dfs1(1,0)

kyori2[N] = 0
dfs2(N,0)

s = 0
f = 0
for k in range(1,N+1):
    if kyori1[k] <= kyori2[k]:
        f += 1
    else:
        s += 1

print("Fennec" if f > s else "Snuke")

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

parent = [-1 for i in range(n)]
dist = [-1 for i in range(n)]
flag = [0 for i in range(n)]

def dfs(s):
    flag[s] = 1
    dist[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag[i]:
                continue
            flag[i] = 1
            parent[i] = v[0]
            dist[i] = v[1] + 1
            q.append((i, d + 1))

parent2 = [-1 for i in range(n)]
dist2 = [-1 for i in range(n)]
flag2 = [0 for i in range(n)]

def dfs_f(s):
    count2 = 0
    flag2[s] = 1
    dist2[s] = 0
    d = 0
    q = deque([(s, d)])
    
    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag2[i]:
                continue
            count2 += 1
            flag2[i] = 1
            parent2[i] = v
            dist2[i] = v[1] + 1
            q.append((i, v[1] + 1))
    return count2

parent3 = [-1 for i in range(n)]
dist3 = [-1 for i in range(n)]
flag3 = [0 for i in range(n)]

def dfs_s(s):
    count3 = 0
    flag3[s] = 1
    dist3[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v]:
            if flag3[i]:
                continue
            count3 += 1
            flag3[i] = 1
            parent3[i] = v[0]
            dist3[i] = v[1] + 1
            q.append((i, v[1] + 1))
    return count3

dfs(0)
D = dist[n-1]

j = n-1
flag2[n-1] = 1
flag3[0] = 1
for i in range(D):
    if (D - i) >= (D+2)//2:
        flag2[j] = 1
        j = parent[j]
    else:
        flag3[j] = 1
        j = parent[j]

df = dfs_f(0)
ds = dfs_s(n-1)

if df > ds:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
g = [[] for i in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

parent = [-1 for i in range(n)]
dist = [-1 for i in range(n)]
flag = [0 for i in range(n)]

def dfs(s):
    flag[s] = 0
    dist[s] = 0
    q = deque(s)
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag[i]:
                continue
            flag[i] = 1
            parent[i] = v
            dist[i] = d
            q.append(i)

parent2 = [-1 for i in range(n)]
dist2 = [-1 for i in range(n)]
flag2 = [0 for i in range(n)]

def dfs_f(s):
    count2 = 0
    flag2[s] = 0
    dist2[s] = 0
    q = deque(s)
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag2[i]:
                continue
            count2 += 1
            flag2[i] = 1
            parent2[i] = v
            dist2[i] = d
            q.append(i)
    return count2

parent3 = [-1 for i in range(n)]
dist3 = [-1 for i in range(n)]
flag3 = [0 for i in range(n)]

def dfs_s(s):
    count3 = 0
    flag3[s] = 0
    dist3[s] = 0
    q = deque(s)
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag2[i]:
                continue
            count3 += 1
            flag2[i] = 1
            parent2[i] = v
            dist2[i] = d
            q.append(i)
    return count3

dfs(0)
D = dist[n-1]

j = n-1
for i in range(D):
    if (D - i) >= (D+2)//2:
        j = parent[j]
        flag2[j] = 1
    else:
        j = parent[j]
        flag3[j] = 1

df = dfs_f(0)
ds = dfs_s(n-1)

if df > ds:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
n = int(input())
p = []
for i in range(n-1):
    p.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in p: 
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
memo = [0] * (n+1)
memo[1] = 1
mi = []
ruto = []
def dfs(start,end,ruto):
  ruto.extend(l[start])
  memo[start] = 1
  while ruto:
    a = ruto.pop()
    mi.append(a)
    if a == n:
      ruto = []
      memo[:] = [1]*(n+1)
      return
    if memo[a] == 1:
      mi.remove(a)
      continue
    dfs(a,end,ruto)
  return
dfs(1,n,ruto)
if len(mi) %2 == 0:
  tigi = [mi[len(mi)//2-1],mi[len(mi)//2]]
else:
  mi.pop()
  if mi == []:
    tigi = [1,n]
  else:
    tigi = [mi[len(mi)//2-1],mi[len(mi)//2]]
l[tigi[0]].remove(tigi[1])
l[tigi[1]].remove(tigi[0])
memo = [0] * (n+1)
memo[1] = 1
ruto = []
def dfsko(start,ruto):
  ruto.extend(l[start])
  memo[start] = 1
  while ruto:
    a = ruto.pop()
    mi.append(a)
    if memo[a] == 1:
      mi.remove(a)
      continue
    dfsko(a,ruto)
  return
dfsko(1,ruto)
kuro = sum(memo)
memo = [0] * (n+1)
memo[n] = 1
ruto = []
dfsko(n,ruto)
siro = sum(memo)
if siro >= kuro:
  print("Snuke")
else:
  print("Fennec")

Submission status: Runtime Error

Solution code:
inf = float("inf")
dist1 = [inf for i in range(n)]

dist1[0] = 0
stk = []
for i in edge[0]:
    stk.append([i,1])

while stk:
    t,c = stk.pop()
    if dist1[t] == inf :
        dist1[t] = c
        for i in edge[t]:
            stk.append([i,c+1])

dist2 = [inf for i in range(n)]
dist2[n-1] = 0
for i in edge[n-1]:
    stk.append([i,1])
while stk:
    t,c = stk.pop()
    if dist2[t] == inf :
        dist2[t] = c
        for i in edge[t]:
            stk.append([i,c+1])

fennec = 0
snuke = 0

for i in range(n):
    if dist1[i] <= dist2[i]:
        fennec += 1
    else :
        snuke += 1
print fennec
print snuke

if fennec > snuke:
    print "Fennec"
else:
    print "Snuke"

Submission status: Runtime Error

Solution code:
def bfs(branch,n,start):
    arrival = [0 for i in range(n+1)]
    q = [start]
    arrival[q[0]]=1
    while len(q) >= 1:
        for k in range(len(branch[q[0]])):
            if arrival[branch[q[0]][k]] == 0:
                arrival[branch[q[0]][k]] = arrival[q[0]] + 1
                q.append(branch[q[0]][k])
        q.pop(0)
    return arrival

def traceback(graph,start,goal,n):
    arrival = bfs(graph,n,start)
    invarrival = bfs(graph,n,goal)
    path = []
    for i in range(2,n):
        if arrival[i] < arrival[goal] and invarrival[i] < invarrival[start]:
            path.append(i)
    return path


n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []
for i in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

path = traceback(graph,1,n,n)
mid = len(path)
start = 1
goal = n

path.reverse()


if len(path) >= 1:
    if len(path)%2 == 0:
        start = path[len(path)//2-1]
    else:
        start = path[len(path)//2]
if len(path) >= 2:
    goal = path[mid-len(path)//2]


graph[goal].remove(start)
arrivalg = bfs(graph,n,goal)
counterg = 0
for i in range(len(arrivalg)):
    if arrivalg[i] > 1:
        counterg += 1
counters = n-2-counterg


if counters > counterg:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
def bfs(branch,n,start):
    arrival = [0 for i in range(n+1)]
    q = [start]
    arrival[q[0]]=1
    while len(q) >= 1:
        for k in range(len(branch[q[0]])):
            if arrival[branch[q[0]][k]] == 0:
                arrival[branch[q[0]][k]] = arrival[q[0]] + 1
                q.append(branch[q[0]][k])
        q.pop(0)
    return arrival

def traceback(graph,start,goal,n):
    arrival = bfs(graph,n,start)
    invarrival = bfs(graph,n,goal)
    path = []
    for i in range(2,n):
        if arrival[i] < arrival[goal] and invarrival[i] < invarrival[start]:
            path.append(i)
    return path
    


n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []
for i in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

path = traceback(graph,1,n,n)
mid = len(path)
start = 1
goal = n

trace = [1]
counter = 0
while counter < mid:
    for i in range(len(graph[trace[counter]])):
        if graph[trace[counter]][i] in path:
            trace.append(graph[trace[counter]][i])
            path.remove(graph[trace[counter]][i])
            counter += 1
            break
trace.pop(0)

if len(trace) >= 1:
    if len(trace)%2 == 0:
        start = trace[len(trace)//2-1]
    else:
        start = trace[len(trace)//2]
if len(trace) >= 2:
    goal = trace[-len(trace)//2+1]

graph[goal].remove(start)
arrivalg = bfs(graph,n,goal)
counterg = 0
for i in range(len(arrivalg)):
    if arrivalg[i] > 1:
        counterg += 1
counters = n-2-counterg


if counters > counterg:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
n = int(input())

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

f = [[0], []]
f[1] = [] + p[0]
if n - 1 in f[1]:
    f[1].remove(n - 1)
    if len(f[1]) == 0:
        print("Snuke")
    else:
        print("Fennec")
    exit()

s = [[n - 1], []]
s[1] = [] + p[n - 1]

d = 1
check = 0
check_f = 0
check_s = 0

while 1:
    if check_f == 0:
        temp_f = []
        for i in f[d]:
            temp_f = temp_f + p[i]
        temp_f = list(set(temp_f))
        if n - 1 in temp_f:
            temp_f.remove(n - 1)
        for i in f[d - 1]:
            if i in temp_f:
                temp_f.remove(i)
        if len(temp_f) > 0:
            f.append([])
            f[d + 1] = [] + temp_f
        else:
            check_f = 1
    else:
        if check_s != 0:
            break

    if check_s == 0:
        temp_s = []
        for i in s[d]:
            temp_s = temp_s + p[i]
        temp_s = list(set(temp_s))
        if 0 in temp_s:
            temp_s.remove(0)
        for i in s[d - 1]:
            if i in temp_s:
                temp_s.remove(i)
        if len(temp_s) > 0:
            s.append([])
            s[d + 1] = [] + temp_s
        else:
            check_s = 1

    if check == 0:
        for i in temp_f:
            if i in temp_s:
                temp_s.remove[i]
                check = 1

    d += 1

fe = sum(len(v) for v in f)

sn = sum(len(v) for v in s)

if fe > sn:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

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


Route = [1]
def dfs(n, np):
    for nc in Node[n]:
        if nc == np:
            continue
        elif nc == N:
            Route.append(N)
            return True
        else:
            Route.append(nc)
            if dfs(nc, n):
                return True
            else:
                Route.pop()
    return False

dfs(1, 0)
b = (len(Route)+1)//2
Node[Route[b-1]].remove(Route[b])
Node[Route[b]].remove(Route[b-1])

cnt = 0
def dfs2(n, np):
    global cnt
    for nc in Node[n]:
        if nc == np:
            continue
        else:
            cnt += 1
            dfs2(nc, n)

dfs2(1, 0)
cnt = -cnt
dfs2(N, 0)
if cnt >= 0:
    print("Snuke")
else:
    print("Fennec")

Submission status: Runtime Error

Solution code:
class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
    
btree = Unionfindtree(N)
wtree = Unionfindtree(N)
N = int(input())
table=[]
for i in range(N-1):
    a,b=map(int,input().split())
    table.append([a-1,b-1])
for x,y in table:
    if x==N-1 or y==N-1:
        continue
    btree.union(x,y)
brack=0
for i in range(N):
    if btree.connect(0,i):
        brack+=1
for x,y in table:
    if x==0 or y==0:
        continue
    wtree.union(x,y)
white=0
for i in range(N):
    if btree.connect(N-1,i):
        white+=1

mid = (brack+white)-N
brack-= mid
white-=mid
if mid %2==0:
    brack+= mid//2
    white+=mid//2
else:
    brack+= (mid//2)+1
    white+=mid//2    
    
if brack>white:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def m():
    def dfs(v, p, c, depth):
        depth[v] = c
        for child in graph[v]:
            if child == p:
                continue
            dfs(child, v, depth[v]+1, depth)
    n = int(input())
    graph = [[] for _ in range(n + 1)]
    depth_from1 = [0] * (n+1)
    depth_fromN = [0] * (n+1)
    depth_from1[1] = 0
    depth_fromN[n] = 0

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

    dfs(1, -1, 0, depth_from1)
    dfs(n, -1, 0, depth_fromN)
    fene = 0
    sn = 0

    for i in range(1,n+1):
        if depth_from1[i] <= depth_fromN[i]:
            fene += 1
        else:
            sn += 1
    if fene > sn:
        return "Fennec"
    else:
        return "Snuke"


print(m())

Submission status: Runtime Error

Solution code:
def m():
    def dfs(v, p, c, depth):
        depth[v] = c
        for child in graph[v]:
            if child == p:
                continue
            dfs(child, v, depth[v]+1, depth)
    n = int(input())
    graph = [[] for _ in range(n + 1)]
    depth_from1 = [0] * (2*n+1)
    depth_fromN = [0] * (2*n+1)
    depth_from1[1] = 0
    depth_fromN[n] = 0

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

    dfs(1, -1, 0, depth_from1)
    dfs(n, -1, 0, depth_fromN)
    fene = 0
    sn = 0

    for i in range(1,n+1):
        if depth_from1[i] <= depth_fromN[i]:
            fene += 1
        else:
            sn += 1
    if fene > sn:
        return "Fennec"
    else:
        return "Snuke"


print(m())

Submission status: Runtime Error

Solution code:
def m():
    def dfs(v, p, c, depth):
        depth[v] = c
        for child in graph[v]:
            if child == p:
                continue
            dfs(child, v, depth[v]+1, depth)
    n = int(input())
    graph = [[] for _ in range(n + 1)]
    depth_from1 = [0] * (n+1)
    depth_fromN = [0] * (n+1)
    depth_from1[1] = 0
    depth_fromN[n] = 0

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

    dfs(1, -1, 0, depth_from1)
    dfs(n, -1, 0, depth_fromN)
    fene = 0
    sn = 0

    for i in range(1,n+1):
        if depth_from1[i] <= depth_fromN[i]:
            fene += 1
        else:
            sn += 1
    if fene > sn:
        return "Fennec"
    else:
        return "Snuke"


print(m())

Submission status: Runtime Error

Solution code:
N = int(input())
g = [[] for _ in range(N+1)]

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


s = ["n"]*(N+1)
s[1] = "b"
s[N] = "w"

def DFS(v):
        global s
        for i in g[v]:
                if s[i] == "w":
                        return
                if s[i] == "n":
                        s[i] = "r"
                        DFS(i)
                        s[i] = "n"

DFS(1)

sb = g[1]
sw = g[N]

while True:
        for i in sb:
                if s[i] == "r":
                        s[i] = "b"
                        sb.extend(g[i])
                        break
        else:
                for i in sb:
                        if s[i] == "n":
                                s[i] = "b"
                                sb.extend(g[i])
                                break
                else:
                        print("Snuke")
                        exit()

        for i in sw:
                if s[i] == "r":
                        s[i] = "w"
                        sw.extend(g[i])
                        break
        else:
                for i in sw:
                        if s[i] == "n":
                                s[i] = "w"
                                sb.extend(g[i])
                                break
                else:
                        print("Fennec")
                        exit()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
int n,a,b;vector<int> g[100005];int d1[100005],d2[100005];void dfs(int r,int f,int d,int dist[]){dist[r]=d;for(int x=0;x<g[r].size();x++)if(g[r][x]!=f)dfs(g[r][x],r,d+1,dist);}int main(){cin>>n;for(int i=0;i<n-1;i++){cin>>a>>b;a--,b--;g[a].push_back(b);g[b].push_back(a);}dfs(0,-1,0,d1);dfs(n-1,-1,0,d2);int ans=0;for(int i=0;i<n;i++)if(d1[i]<=d2[i])ans++;else ans--;if(ans>0)cout <<"Fennec"<< endl;else cout<<"Snuke"<<endl;}

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(N+1)]
for_in range(N-1):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)
F=["" for i in range(N+1)]
S=["" for i in range(N+1)]
visited = [False for i in range(N+1)]
Q = deque([(1, 0)])
while len(Q):
    m, d = Q.popleft()
    if visited[m]:
        continue
    else:
        F[m] = d
        visited[m] = True
    for nm in G[m]:
        Q.append((nm, d+1))
visited = [False for i in range(N+1)]
Q = deque([(N, 0)])
while len(Q):
    m, d = Q.popleft()
    if visited[m]:
        continue
    else:
        S[m]=d
        visited[m]=True
    for nm in G[m]:
        Q.append((nm, d+1))
black = 0    
for i in range(1, N+1):
    if F[i]<=S[i]:
        black+=1
if 2*black>N:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
N = int(input())
fen_count = 0
E = [dict() for _ in range(N+1)]
for i in range(N-1):
	a,b = map(int,input().split(" "))
	E[a][b] = 1
	E[b][a] = 1

def dfs(ver,prev,rank):
	global fen_count
	flag = -1
	fen_count += 1
	for nextver in E[ver].keys():
		if nextver == prev:
			pass
		elif nextver == N:
			flag = rank
		else:
			flag = max(dfs(nextver,ver,rank+1),flag)

	if flag >= 0:
		return flag
	else:
		return -1

between = dfs(1,-1,0)
ans = fen_count - between 
if between % 2 == 0:
	ans += between // 2
else:
	ans += ((between // 2)+1)


if ans > (N-2-ans):
	print("Fennec")
else:
	print("Snuke")

Submission status: Runtime Error

Solution code:
N = int(input())
fen_count = 0
E = [dict() for _ in range(N+1)]
for i in range(N-1):
	a,b = map(int,input().split(" "))
	E[a][b] = 1
	E[b][a] = 1

def dfs(ver,prev,rank):
	global fen_count
	flag = -1
	fen_count += 1
	for nextver in E[ver].keys():
		if nextver == prev:
			continue
		elif nextver == N:
			flag = 1
		else:
			flag = max(dfs(nextver,ver,rank+1),flag)

	if flag >= 0:
		return rank
	else:
		return -1

between = dfs(1,-1,0)
ans = fen_count - between 
if between % 2 == 0:
	ans += between // 2
else:
	ans += ((between // 2)+1)


if ans > (N-ans):
	print("Fennec")
else:
	print("Snuke")

Submission status: Runtime Error

Solution code:
N = int(input())
adj = [[] for n in range(N)]
for i in range(N-1):
  a, b = [int(n)-1 for n in input().split()]
  adj[a].append(b)
  adj[b].append(a)



def dfs(now, cost, dic):
  dic[now] = cost
  for nx in adj[now]:
    if nx not in dic:
      dfs(nx, cost+1, dic)

dist_f = {}
dist_s = {}

dfs(0, 0, dist_f)
dfs(N-1, 0, dist_s)


f_cnt = 0
for  i in range(N):
  if dist_f[i] <= dist_s[i]:
    f_cnt += 1

if f_cnt > N-f_cnt:
  print("Fennec")
else:
  print("Snuke")

Submission status: Runtime Error

Solution code:
N = int(input())
adj = [[] for n in range(N)]
for i in range(N-1):
  a, b = [int(n)-1 for n in input().split()]
  adj[a].append(b)
  adj[b].append(a)



def dfs(now, cost, dic):
  dic[now] = cost
  for nx in adj[now]:
    if nx not in dic:
      dfs(nx, cost+1, dic)

dist_f = {}
dist_s = {}

dfs(0, 0, dist_f)
dfs(N-1, 0, dist_s)


f_cnt = 0
for  i in range(N):
  if dist_f[i] <= dist_s[i]:
    f_cnt += 1

if f_cnt >= N-f_cnt:
  print("Fennec")
else:
  print("Snuke")

Submission status: Runtime Error

Solution code:
import sys

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

depth = [None]*(N+1)
def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
DFS(1,0,0)

depthN = [None]*(N+1)
def DFSN(v,p,d):
    depthN[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFSN(e[0], v, d + e[1])
DFSN(N,0,0)

black = 0
for i in range(1,N):
    if depth[i] <= depthN[i]:
        black += 1

if black > N/2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import copy

def calcDist(x, i_list, j, l):
	if len(i_list) == 0:
		return N
	min = N
	for i in i_list:
		if i == j:
			return l
		if not i in chains:
			chains[i] = []
		i_list_c = copy.copy(chains[i])
		if x in i_list_c:
			i_list_c.remove(x)
		m = calcDist(i, i_list_c, j, l + 1)
		if min > m:
			min = m

	return min


N = int(sys.stdin.readline())

chains = {}

for i in range(0, N - 1):
	line = list(map(int, sys.stdin.readline().split(' ')))
	if not line[0] in chains:
		chains[line[0]] = []
	chains[line[0]].append(line[1])
	if not line[1] in chains:
		chains[line[1]] = []
	chains[line[1]].append(line[0])

b = 0
w = 0
for i in range(2, N):
	bd = calcDist(1, chains[1], i, 0)
	wd = calcDist(N, chains[N], i, 0)
	if bd <= wd:
		b += 1
	else:
		w += 1

if b > w:
	print ('Fennec')
else:
	print ('Snuke')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import copy

def calcDist(x, i_list, j, l):
	if len(i_list) == 0:
		return N
	min = N
	for i in i_list:
		if i == j:
			return l
		i_list_c = copy.copy(chains[i])
		if x in i_list_c:
			i_list_c.remove(x)
		m = calcDist(i, i_list_c, j, l + 1)
		if min > m:
			min = m

	return min


N = int(sys.stdin.readline())

chains = {}

for i in range(0, N - 1):
	line = list(map(int, sys.stdin.readline().split(' ')))
	if not line[0] in chains:
		chains[line[0]] = []
	chains[line[0]].append(line[1])
	if not line[1] in chains:
		chains[line[1]] = []
	chains[line[1]].append(line[0])

b = 0
w = 0
for i in range(2, N):
	bd = calcDist(1, chains[1], i, 0)
	wd = calcDist(N, chains[N], i, 0)
	if bd <= wd:
		b += 1
	else:
		w += 1

if b > w:
	print ('Fennec')
else:
	print ('Snuke')