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:
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1]*(n+1)
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    preference= [None]*(n+1)#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while Q:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

n=int(input())
d=defaultdict(list)

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

x,y=DIJKSTRA(n,d)
#print(x,y)
point=1
pre=[1]
while point!=n:
    point=x[point]
    pre.append(point)
#print(pre)

if len(pre)%2==0:
    l.remove([pre[len(pre)//2-1],pre[len(pre)//2]])
else:
    l.remove([pre[len(pre)//2],pre[len(pre)//2+1]])
#print(l)
u=UNION_FIND(n+1)

for k,v in l:
    u.union(k,v)
if u.size(1)>u.size(n):
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1]*(n+1)
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    preference= [None]*(n+1)#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while Q:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

n=int(input())
d=defaultdict(list)

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

x,y=DIJKSTRA(n,d)
#print(x,y)
point=1
pre=[1]
while point!=n:
    point=x[point]
    pre.append(point)
#print(pre)

if len(pre)%2==0:
    l.remove([pre[len(pre)//2-1],pre[len(pre)//2]])
else:
    l.remove([pre[len(pre)//2],pre[len(pre)//2+1]])
#print(l)
u=UNION_FIND(n+1)

for k,v in l:
    u.union(k,v)
if u.size(1)>u.size(n):
    print("Fennec")
else:
    print("Sunuke")

Submission status: Runtime Error

Solution code:
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1]*(n+1)
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    preference= [None]*(n+1)#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while Q:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

n=int(input())
d=defaultdict(list)

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

x,y=DIJKSTRA(n,d)
#print(x,y)
point=1
pre=[1]
while point!=n:
    point=x[point]
    pre.append(point)
#print(pre)

if len(pre)%2==0:
    l.remove([pre[len(pre)//2-1],pre[len(pre)//2]])
else:
    l.remove([pre[len(pre)//2],pre[len(pre)//2+1]])
#print(l)
u=UNION_FIND(n+1)

for k,v in l:
    u.union(k,v)
if u.size(1)>u.size(n):
    print("Sunuke")
else:
    print("Fennec")

Submission status: Runtime Error

Solution code:
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1]*(n+1)
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    preference= [None]*(n+1)#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while Q:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

n=int(input())
d=defaultdict(list)

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

x,y=DIJKSTRA(n,d)
if x[1]!=n:
    point=1
    pre=[1]
#    print(x,y)
    while point!=n:
        pre.append(x[point])
        point=x[x[point]]
    pre.append(point)
else:
    pre=[1,n]


if len(pre)%2:
    try:
        l.remove((pre[len(pre)//2],pre[len(pre)//2+1]))
    except:
        l.remove((pre[len(pre)//2+1],pre[len(pre)//2]))
else:
    try:
        l.remove((pre[len(pre)//2-1],pre[len(pre)//2]))
    except:
        l.remove((pre[len(pre)//2],pre[len(pre)//2-1]))
u=UNION_FIND(n+1)
for k,v in l:
    u.union(k,v)
if u.size(1)>u.size(n):
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
def dfs(route):
    v0 = route[-1]
    if v0 == 0:
        for v in edges[0]:
            if v == N-1:
                return route+[N-1]
            res = dfs(route+[v])
            if res:
                return res
    if len(edges[v0]) == 1:
        return False
    for v in edges[v0]:
        if v == N-1:
            return route+[N-1]
        if v != route[-2]:
            res = dfs(route+[v])
            if res:
                return res
    return False
route = dfs([0])
i = (len(route)+1)//2 
a, b = route[i-1:i+1]
edges[a].remove(b)
edges[b].remove(a)
que = deque([0])
flag = [True]*N
score = 0
while que:
    v0 = que.pop()
    score+=1
    for v in edges[v0]:
        if flag[v]:
            que.append(v)
            flag[v] = False
if score>N//2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
N = int(input())

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

"""
相手の取れるマス目を減らすようにとるとよい
相手よりそのマスに近ければそのマスを取得できる
フェネックくん、すぬけ君について初期地点からそれぞれへの距離が必要
"""
def solve(now, depth, depth_list, es, visited):
    visited[now] = True
    depth_list[now] = depth
    for next in es[now]:
        if visited[next] == False:            
            solve(next, depth+1, depth_list, es, visited)

depth_list_F = [0] * N
visited_F = [False] * N
solve(0, 0, depth_list_F, es, visited_F)

depth_list_S = [0] * N
visited_S = [False] * N
solve(N-1, 0, depth_list_S, es, visited_S)

cnt_F = cnt_S = 0
for f,s in zip(depth_list_F, depth_list_S):
    if f <= s:
        cnt_F += 1 # フェネック君から始めるので同じ距離ならフェネック君がとる
    else:
        cnt_S += 1

if cnt_F > cnt_S:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
N=int(input())
edges=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    edges[A-1].append(B-1)
    edges[B-1].append(A-1)
prevs=[0]*N
def dfs(prev,curr):
    prevs[curr]=prev
    if curr == N-1:
        return
    for c in edges[curr]:
        if c!=prev:
            dfs(curr,c)
dfs(-1,0)
paths=[N-1]
tmp=N-1
while tmp!=0:
    paths.append(prevs[tmp])
    tmp=prevs[tmp]

points=[0,0]
def count(prev,curr,player):
    points[player]+=1
    for c in edges[curr]:
        if c!=prev:
            count(curr,c,player)

nf = (len(paths)+1)//2
f,s = paths[nf-1],paths[nf]
count(s,f,0)
count(f,s,1)
pf,ps=points
print("Fennec" if pf>ps else "Snuke")

Submission status: Runtime Error

Solution code:
N=int(input())
edges=[[] for _ in range(N)]
for _ in range(N):
    A,B=map(int,input().split())
    edges[A-1].append(B-1)
    edges[B-1].append(A-1)
prevs=[0]*N
def dfs(prev,curr):
    prevs[curr]=prev
    if curr == N-1:
        return
    for c in edges[curr]:
        if c!=prev:
            dfs(curr,c)
dfs(-1,0)
paths=[N-1]
tmp=N-1
while tmp!=0:
    paths.append(prevs[tmp])
    tmp=prevs[tmp]

points=[0,0]
def count(prev,curr,player):
    points[player]+=1
    for c in edges[curr]:
        if c!=prev:
            count(curr,c,player)

nf = (len(paths)+1)//2
f,s = paths[nf-1],paths[nf]
count(s,f,0)
count(f,s,1)
pf,ps=points
print("Fennec" if pf>ps else "Snuke")

Submission status: Runtime Error

Solution code:
import math

N=int(input())

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

depth=[[0]*N for i in range(2)]

def dfs(d, i, p, k=0):
	for t in G[i]:
		if t!=p:
			depth[k][t]=d
			dfs(d+1, t, i,k)
			


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

cnt=0
for i,j in zip(depth[0], depth[1]):
	if i<=j:
		cnt+=1

print('Fennec' if cnt*2>N else 'Snuke')

Submission status: Runtime Error

Solution code:
import math

N=int(input())

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


seen=[False]*N
seen[0]=True
depth=[0]*N
sub_tree=[1]*N
ne=[0]


def dfs(d, i, p):
	for t in G[i]:
		if t!=p:
			depth[t]=d
			dfs(d+1, t, i)
			
			sub_tree[i]+=sub_tree[t]



dfs(1,0,-1)

d=depth[-1]
a=sub_tree[0]-sub_tree[-1]-d
b=sub_tree[-1]-1

a+=math.ceil(d/2)
b+=d//2

print('Fennec' if a>b else 'Snuke')

Submission status: Runtime Error

Solution code:
# ABC067D - Fennec VS. Snuke (ARC078D)
import sys

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


def dfs(v: int, x: int, y: int) -> None:
    D[y][v] = x
    for u in G[v]:
        if not D[y][u]:
            dfs(u, x + 1, y)


def main():
    global G, D
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    D = [[0] * (N + 1) for _ in range(2)]
    dfs(1, 1, 0), dfs(N, 1, 1)
    b, w = 0, 0
    for i, j in zip(*D[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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)

def dfs(p, checked, now):
    #print(p, checked, now)
    if p == N-1:
        return now, True
    ok = False
    for q in graph[p]:
        if not checked[q]:
            now.append(q)
            checked[q] = True
            bw, ok = dfs(q, checked, now)
    if not ok:
        now.pop()
        return now, False
    return bw, True

checked = [False for _ in range(N)]
checked[0] = True
bw, ok = dfs(0, checked, [0])
#print(bw)
cb = len(bw) - 2

between = [False for _ in range(N)]
for b in bw:
    between[b] = True

def dfs2(p, checked, c):
    c += 1
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(0, between, 0)-1
cN = dfs2(N-1, between, 0)-1
#print(c0, cN)

if cb % 2 == 0:
    c0 += cb//2
    cN += cb//2
else:
    c0 += cb//2+1
    cN += cb//2

if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
ki=[[] for i in range(n+1)]
for i in range(n-1):
    ki[ab[i][0]].append(ab[i][1])
    ki[ab[i][1]].append(ab[i][0])
# print(ki)
kyori=[[0,0] for i in range(n+1)]
def tansaku(m, dis, hito):
    if not ki[m]:
        kyori[m][hito]=dis
        return
    elif kyori[m][hito]!=0:
        return
    else:
        kyori[m][hito]=dis
        for i in range(len(ki[m])):
            tansaku(ki[m][i], dis+1, hito)
tansaku(1,1,0)
tansaku(n,1,1)
fe,su=0,0

for i in range(1,n+1):
    if kyori[i][0]<=kyori[i][1]:
        fe+=1
    else:
        su+=1

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

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
ki=[[] for i in range(n+1)]
for i in range(n-1):
    ki[ab[i][0]].append(ab[i][1])
    ki[ab[i][1]].append(ab[i][0])
# print(ki)
kyori=[[0,0] for i in range(n+1)]
def tansaku(m, dis, hito):
    if not ki[m]:
        kyori[m][hito]=dis
        return
    elif kyori[m][hito]!=0:
        return
    else:
        kyori[m][hito]=dis
        for i in range(len(ki[m])):
            tansaku(ki[m][i], dis+1, hito)
tansaku(1,1,0)
tansaku(n,1,1)
fe,su=0,0

for i in range(1,n+1):
    if kyori[i][0]<=kyori[i][1]:
        fe+=1
    else:
        su+=1

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

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
ki=[[] for i in range(n+1)]
for i in range(n-1):
    ki[ab[i][0]].append(ab[i][1])
    ki[ab[i][1]].append(ab[i][0])
# print(ki)
kyori=[[0,0] for i in range(n+1)]
def tansaku(m, dis, hito):
    if not ki[m]:
        kyori[m][hito]=dis
        return
    elif kyori[m][hito]!=0:
        return
    else:
        kyori[m][hito]=dis
        for i in range(len(ki[m])):
            # print(m)
            tansaku(ki[m][i], dis+1, hito)
tansaku(1,1,0)
tansaku(n,1,1)
fe,su=0,0

for i in range(1,n+1):
    if kyori[i][0]<kyori[i][1]:
        fe+=1
    else:
        su+=1

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

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
ki=[[] for i in range(n+1)]
for i in range(n-1):
    ki[ab[i][0]].append(ab[i][1])
    ki[ab[i][1]].append(ab[i][0])
# print(ki)
kyori=[[0,0] for i in range(n+1)]
def tansaku(m, dis, hito):
    if not ki[m]:
        kyori[m][hito]=dis
        return
    elif kyori[m][hito]!=0:
        return
    else:
        kyori[m][hito]=dis
        for i in range(len(ki[m])):
            tansaku(ki[m][-1-i], dis+1, hito)
tansaku(1,1,0)
tansaku(n,1,1)
fe=0
su=0
for i in range(n+1):
    if kyori[i][0]<kyori[i][1]:
        fe+=1
    elif kyori[i][0]>kyori[i][1]:
        su+=1
    else:
        pass
if fe>su:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
n=int(input())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
def f(a,b):
    c,flag,ans=[[a,[0,a]]],False,[]
    while c or flag=False:
        p,q=c.pop()
        for i in s[p]:
            if i==b:
                ans=q[1:]+[b]
                break
            else:
                if q[-2]!=i:
                    c.append([i,q+[i]])
    else:
        return ans
def f(x,l):
    c=0
    p,d=[x],[0]*(n+1)
    while p:
        a=p.pop()
        if a not in x or a==x:
            c+=1
            d[a]=1
            for i in s[a]:
                if d[i]==0:
                    p.append(i)
    else:
        return c
t=f(a,b)
t=[f(i,ans)for i in t]
print("Fennec"if sum(t[:-len(t)//2])>sum(t[-len(t)//2:]) else"Snuke")

Submission status: Runtime Error

Solution code:
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)
stack1=deque(G[0])
stack2=deque(G[N-1])
X=[-1]*N
X[0]=1
X[N-1]=0
while(stack1 or stack2):
    Stack1=deque()
    for i in stack1:
        if X[i]==-1:
            X[i]=1
            for j in G[i]:
                if X[j]==-1:
                    Stack1.append(j)
    stack1=Stack1
    Stack2=deque()
    for i in stack2:
        if X[i]==-1:
            X[i]=0
            for j in G[i]:
                if X[j]==-1:
                    Stack2.append(j)
    stack2=Stack2
f,s=0,0
for i in range(N):
    if X[i]==1:
        f+=1
    else:
        s+=1
if f>s:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)
    def find_path(idx, target, conn, visited):
        visited[idx] = True
        if idx == target:
            return [target]
        for nex in conn[idx]:
            if not visited[nex]:
                path = find_path(nex, target, conn, visited)
                if path is not None:
                    return [idx] + path
        return None

    visited = [False] * N
    path_to_n = find_path(0, N - 1, conn, visited)
    #print(path_to_n)

    colors = [None] * N
    for i, node in enumerate(path_to_n):
        if i < (len(path_to_n) + 1) / 2:
            colors[node] = True
        else:
            colors[node] = False

    def dfs(idx, conn, colors):
        colors[idx] = True
        for nex in conn[idx]:
            if colors[nex] is None:
                dfs(nex, conn, colors)
        return

    cnt = 0
    dfs(0, conn, colors)
    #print(colors)
    for c in colors:
        if c:
            cnt += 1
    if cnt > (N - cnt):
        ret = 'Fennec'
    else:
        ret = 'Snuke'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

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)
dist1 = [0]*(N+1)
def func1(now, prv, d):
    dist1[now] = d
    for p in G[now]:
        if p != prv:
            func1(p, now, d+1)
func1(1, 0, 0)

fen = 0
sun = 0
d = dist1[N]
d1 = d//2
for i in dist1[1:]:
    if i <= d1:
        fen += 1
    else:
        sun += 1
if fen > sun:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
# 木グラフなので各プレイヤから近い点の個数を比べればよい

N = int(input())

edge = [[] for _ in range(N)]

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

INF = 10**18

d_fe = [INF]*N
d_sn = [INF]*N

d_fe[0] = 0
d_sn[-1] = 0

def f(d,x):
  dx = d[x]
  for v in edge[x]:
    if d[v] == INF:
      d[v] = dx+1
      f(d,v)
      
f(d_fe,0)
f(d_sn,N-1)

black = 0
white = 0

for x in range(N):
  if d_fe[x] <= d_sn[x]:
    black += 1
  else:
    white += 1

answer = 'Fennec' if black > white else 'Snuke'
print(answer)

Submission status: Runtime Error

Solution code:
// Created by sz
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, d1[N], dn[N];

vector<int> g[N];


void dfs(int u, int pre,int* d ){
    
    for(auto i: g[u]){
        if (i==pre)continue;
        d[i] = d[pre] + 1;
        dfs(i, u, d);
    }
}

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    
    int a,b;
    for (int i = 1; i <= n-1; i++){
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    
    dfs(1, -1, d1);
    dfs(n, -1, dn);
    
    int ans = 0;
    for (int i = 2; i <= n-1; i++){
        if(d1[i]<= dn[i])ans++;
        else ans --;
    }
    
    if(ans >0) cout<<"Fennec"<<endl;
    else cout<<"Snuke"<<endl;
    
    
    
    
    
    return 0;
}

Submission status: Runtime Error

Solution code:
n = int(input())
ab = [[int(item) for item in input().split()] for _ in range(n-1)]

e = [[] for _ in range(n)]
for a, b in ab:
    e[a-1].append(b-1)
    e[b-1].append(a-1)

shortest = []
def get_path(start, end, par, path):
    global shortest
    if end in e[start]:
        shortest = path + [end]
        return shortest
    for item in e[start]:
        if item != par:
             get_path(item, end, start, path + [item])

def tree_count(start, par, a, b):
    count = 0
    for item in e[start]:
        if start == a and item == b:
            continue
        if start == b and item == a:
            continue
        if item != par:
            count += 1
            count += tree_count(item, start, a, b)
    return count

get_path(0, n-1, -1, [0])
cut_l = (len(shortest)-1) // 2
p = tree_count(0, -1, shortest[cut_l], shortest[cut_l+1])
q = tree_count(n-1, -1, shortest[cut_l], shortest[cut_l+1])

if p > q:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Runtime Error

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

def bfs(x):
    cnt=0
    q=deque()
    q.append(x)
    vst=set()
    while len(q)>0:
        c=q.popleft()
        vst.add(c)
        for nb in g[c]:
            if nb not in vst:
                q.append(nb)
    return vst

def dfs(x,y,path,vst):
    path=deque(path)
    vst=deque(vst)
    path.append(x)
    vst.append(x)
    if x==y:
        return path
    
    for i in g[x]:
        if i not in vst:
            a=dfs(i,y,path,vst)
            if a!=None:
                return a

r=dfs(1,n,deque(),deque())
rl=list(r)
t=(len(rl)-1)//2
g[rl[t]].remove(rl[t+1])
#print(rl)

print('Fennec' if len(bfs(1))>=n//2 else 'Snuke')

Submission status: Runtime Error

Solution code:
def dfs(v, d, path):
    # 頂点(0, N - 1)間の最短距離を求める
    # m_dist[v]:=頂点0からの最短距離
    res = []
    if m_dist[v] < float('inf'):
        return
    m_dist[v] = min(m_dist[v], d)
    if v == N - 1:
        return path
    for nv in e[v]:
        ret = dfs(nv, d + 1, path + [nv])
        if ret:
            res = ret
            break
    return res


def dfs_to_color(v, my_color):
    # 着色可能な範囲を着色する
    # 自分の色（黒、白）の幹から出ている未着色のマスが着色可能
    if m_bl[v]: return
    m_bl[v] = True
    if m[v] == my_color or m[v] == None:
        m[v] = my_color
        for nv in e[v]:
            dfs_to_color(nv, my_color)


N = int(input())
m = [None for _ in range(N)]
m[0] = True
m[N - 1] = False
# 色, 0-indexed
# True == 黒 == Fennec
# False == 白 == Snuke
m_dist = [float('inf') for _ in range(N)]
# 頂点0からの距離
m_bl = [False for _ in range(N)]
# 着色作業が完了したか

e = [[] for _ in range(N)]
# 道, 隣接リスト, 0-indexed

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

path = dfs(0, 0, [0])
# 頂点(0, N - 1)間の最短距離をm_dist[N-1]に代入
# 最短パスを返す

for p in path:
    if m_dist[p] <= abs(m_dist[N - 1] - m_dist[p]):
        # 頂点0から近い場合
        # 等距離なら先に塗れる黒になる
        m[p] = True
        # 黒
    else:
        # 頂点N-1から近い場合
        m[p] = False
        # 白
# 最短経路を先に着色する

dfs_to_color(0, True)
# Fennec

dfs_to_color(N - 1, False)
# Snuke

print('Fennec' if m.count(True) > m.count(False) else 'Snuke')

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    x,y = map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)

def dfs(v):
    d = [-1 for i in range(n)]
    q = []
    d[v] = 0
    q.append(v)
    while len(q):
        v = q.pop()
        for i in a[v]:
            if d[i] == -1:
                d[i] = d[v]+1
                q.append(i)
    return d
c1 = dfs(0)
c2 = dfs(n-1)
c = 0
for i in range(n):
    if c1[i]>c2[i]:
        c += 1
if c>= n/2:
    print("Snuke")
else:
    print("Fennec")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
g = [[] for i in range(N)]
 
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    g[a] += [b]
    g[b] += [a]
    
def bfs(g, st):
    queue = [st]
    distances = [-1 for i in range(N)]
    distances[st] = 0
    
    while queue:
        node = queue.pop(0)
        for h in g[node]:
            if distances[h] == -1:
                distances[h] = distances[node] + 1
                queue += h
 
    return distances
 
dB = bfs(g, 0)
dW = bfs(g, N-1)
 
B, W = 0, 0
for i in range(N):
    if dB[i] <= dW[i]:
        B += 1
    else:
        W += 1
print("Fennec" if B > W else "Snuke")

Submission status: Runtime Error

Solution code:
def dps(road,dist,node,d):
    for x in road[node]:
        if dist[x]<0:
            dist[x]=d
            dps(road,dist,x,d+1)
    
N=int(input())
road=[[] for _ in range(N)]
f_d=[-1 for _ in range(N)]
s_d=[-1 for _ in range(N)]
f_d[0]=0
s_d[-1]=0

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)

dps(road,f_d,0,1)
dps(road,s_d,N-1,1)

white=0
black=0

for i in range(N-1):
    if f_d[i]<=s_d[i]:
        white+=1
    else:
        black+=1

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