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

Solution (Python):

import sys
from collections import deque


inf = float('inf')

def solve(N: int, a: "List[int]", b: "List[int]"):
    adj = [set() for _ in range(N)]
    for u, v in zip(a, b):
        adj[u].add(v)
        adj[v].add(u)
    
    dist_F = [inf for _ in range(N)]
    dist_F[0] = 0
    dist_S = [inf for _ in range(N)]
    dist_S[N-1] = 0

    Q = deque([(0, 0)], N)
    while len(Q) > 0:
        du, u = Q.pop()
        for v in adj[u]:
            if dist_F[v] < inf:
                continue
            dist_F[v] = du + 1
            Q.append((du+1, v))
    

    Q = deque([(0, N-1)], N)
    while len(Q) > 0:
        du, u = Q.pop()
        for v in adj[u]:
            if dist_S[v] < inf:
                continue
            dist_S[v] = du + 1
            Q.append((du+1, v))

    c_S = 0
    c_F = 0

    for df, ds in zip(dist_F, dist_S):
        if df <= ds:
            c_F += 1
        else:
            c_S += 1

    if c_F <= c_S:
        print('Snuke')
    else:
        print('Fennec')    

    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))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens)) - 1
        b[i] = int(next(tokens)) - 1
    solve(N, a, b)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def dfs(graph, start):
    stack = deque()
    costs = [0] * (N+1)
    stack.append([start,0])
    costs[start] = -1
    while stack:
        a, cost = stack.popleft()
        for b in graph[a].keys():
            if not costs[b]:
                stack.append([b,cost+1])
                costs[b] = cost+1
    return costs

N = int(input())
graph = {}
for i in range(N-1):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
f_costs = dfs(graph,1)
s_costs = dfs(graph,N)
f_cnt = 1
for i in range(2,N):
    if f_costs[i] <= s_costs[i]:
        f_cnt += 1

print('Fennec' if f_cnt > N - f_cnt else 'Snuke')

Solution (Python):





import sys
sys.setrecursionlimit(1000000)

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


col = [ -1 for i in range(N)]
col[0] = 0
p = []
path = [ 0 for i in range(10**5+1)]
def dfs(n,c):
    global p
    if n == N - 1:
        p = path
    path[c] = n
    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            dfs(v,c+1)
            if p:
                return
dfs(0,0)

t = col[N-1] + 1
if t % 2 ==0:
    sn = p[t//2]
else:
    sn = p[t//2+1]



colfn = [ -1 for i in range(N)]
colfn[0] = 0
def dfs2(n,c):

    for v in e[n]:
        if v == sn:
            continue
        elif colfn[v] == -1:
            colfn[v] = c + 1
            dfs2(v,c+1)

dfs2(0,0)

fennec = -1
for i in range(N):
    if colfn[i] != -1:
        fennec += 1



snuke = N - fennec - 2

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

Solution (Python):

import sys
sys.setrecursionlimit(1000000)

N = int(input())

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

col = [ -1 for i in range(N)]
col[0] = 0

p = []
path = [ 0 for i in range(10**5+1)]
def dfs(n,c):
    global p
    if n == N - 1:
        p = path
    path[c] = n
    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            dfs(v,c+1)
            if p:
                return
dfs(0,0)

t = col[N-1] + 1
if t % 2 ==0:
    sn = p[t//2]
else:
    sn = p[t//2+1]


colfn = [ -1 for i in range(N)]
colfn[0] = 0
def dfs2(n,c):

    for v in e[n]:
        if v == sn:
            continue
        elif colfn[v] == -1:
            colfn[v] = c + 1
            dfs2(v,c+1)

dfs2(0,0)

fennec = -1
for i in range(N):
    if colfn[i] != -1:
        fennec += 1

snuke = N - fennec - 2
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

import sys

p = []
path = [ 0 for i in range(10**5+1)]
def main():

    sys.setrecursionlimit(1000000)

    N = int(input())

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

    col = [ -1 for i in range(N)]
    col[0] = 0
    
    def dfs(n,c):
        global p
        if n == N - 1:
            p = path
        path[c] = n
        for v in e[n]:
            if col[v] == -1:
                col[v] = c + 1
                dfs(v,c+1)
                if p:
                    return
    dfs(0,0)

    t = col[N-1] + 1
    if t % 2 ==0:
        sn = p[t//2]
    else:
        sn = p[t//2+1]


    colfn = [ -1 for i in range(N)]
    colfn[0] = 0
    def dfs2(n,c):

        for v in e[n]:
            if v == sn:
                continue
            elif colfn[v] == -1:
                colfn[v] = c + 1
                dfs2(v,c+1)

    dfs2(0,0)

    fennec = -1
    for i in range(N):
        if colfn[i] != -1:
            fennec += 1

    snuke = N - fennec - 2
    if fennec > snuke:
        print("Fennec")
    else:
        print("Snuke")



if __name__ == '__main__':
    main()

Solution (Python):
import sys

p = []
path = [ 0 for i in range(10**5+1)]
def main():

    sys.setrecursionlimit(1000000)

    N = int(input())

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

    col = [ -1 for i in range(N)]
    col[0] = 0
    
    
    def dfs(n,c):
        global p
        
        
        
        if n == N - 1:
            p = path
        path[c] = n
        for v in e[n]:
            if col[v] == -1:
                col[v] = c + 1
                dfs(v,c+1)
                
                if p:
                    return
    dfs(0,0)
    
    

    t = col[N-1] + 1
    if t % 2 ==0:
        sn = p[t//2]
    else:
        sn = p[t//2+1]


    colfn = [ -1 for i in range(N)]
    colfn[0] = 0
    def dfs2(n,c):

        for v in e[n]:
            if v == sn:
                continue
            elif colfn[v] == -1:
                colfn[v] = c + 1
                dfs2(v,c+1)

    dfs2(0,0)

    fennec = -1
    for i in range(N):
        if colfn[i] != -1:
            fennec += 1

    snuke = N - fennec - 2
    if fennec > snuke:
        print("Fennec")
    else:
        print("Snuke")



if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def dfs(graph, start, goal):
    s_stack = deque()
    g_stack = deque()
    visited = [0 for i in range(N+1)]
    s_stack.append([start,0])
    g_stack.append([goal, 0])
    visited[start] = 1 
    visited[goal] = 1 
    s_cnt = 1
    g_cnt = 1
    round = 0
    while s_stack or g_stack:
        while s_stack:
            a,cost = s_stack.popleft()
            if cost > round:
                s_stack.appendleft([a,cost])
                break
            for b in graph[a].keys():
                if not visited[b]:
                    s_stack.append([b,cost+1])
                    visited[b] += 1 
                    s_cnt += 1
        while g_stack:
            a, cost = g_stack.popleft()
            if cost > round:
                g_stack.appendleft([a,cost])
                break
            for b in graph[a].keys():
                if not visited[b]:
                    g_stack.append([b,cost+1])
                    visited[b] += 1 
                    g_cnt += 1
        round += 1
    
    return s_cnt > g_cnt

N = int(input())
graph = {}
for i in range(N-1):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
print('Fennec' if dfs(graph,1,N) else 'Snuke')

Solution (Python):
N=int(input())
edge=[list(map(int,input().split())) for i in range(N-1)]
inf=10**20
c=[[] for i in range(N)]
for i,j in edge:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
d=[0]+[inf]*(N-1)
v=[0]*N
import sys
sys.setrecursionlimit(10**6)
def dfs(p,v,d):
    for n in c[p]:
        if v[n]==0:
            d[n]=min(d[n],d[p]+1)
            v[n]=1
            dfs(n,v,d)
dfs(0,v,d)
d2=[inf]*(N-1)+[0]
v=[0]*N
dfs(N-1,v,d2)
c=0
for i,j in zip(d,d2):
    c=c+1 if i<=j else c-1
print(['Snuke','Fennec'][c>0])

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(graph: list, start: int):
    n = len(graph)
    dist = [-1]*n

    que = deque([(start, 0)])

    while que:
        cur_node, cur_dist = que.popleft()
        dist[cur_node] = cur_dist

        for nex in graph[cur_node]:
            if dist[nex] < 0:
                dist[nex] = cur_dist + 1
                que.append((nex, cur_dist+1))

    return dist

n = ni()

graph = [[] for _ in range(n)]
for _ in range(n-1):
    x, y = li_()
    graph[x].append(y)
    graph[y].append(x)

fenec = bfs(graph, 0)
snuke = bfs(graph, n-1)

fenec_saki = 0
for d1, d2 in zip(fenec, snuke):
    if d1 <= d2:
        fenec_saki += 1
    elif d1 > d2:
        fenec_saki -= 1

if fenec_saki == 0:
    if n%2:
        print("Fennec")
    else:
        print("Snuke")

elif fenec_saki > 0:
    print("Fennec")

else:
    print("Snuke")

Solution (Python):

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

vi = 0 
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
prev_list = [-1 for i in range(N)]
min_path_list = [10**27 for i in range(N)] 
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            prev_list[v1]=v
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) 

path = [N-1]
v=N-1
while prev_list[v]!=-1:
    path.append(prev_list[v])
    v=prev_list[v]

a=path[(min_path_list[N-1]-1)//2]
b=path[(min_path_list[N-1]-1)//2+1]
for i in range(len(e_list[a])):
    if e_list[a][i]==b:
        break
del e_list[a][i]

for i in range(len(e_list[b])):
    if e_list[b][i]==a:
        break
del e_list[b][i]

vi = 0 

Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
count = 1
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            count+=1

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

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())


N = int(input())



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



for _ in range(N-1):
  a,b = mi()
  a -= 1
  b -= 1
  ngb[a].append(b)
  ngb[b].append(a)

start = 0
goal = N-1



nodes = [[-1, -1] for _ in range(N)]


nodes[start][0] = 0
nodes[start][1] = -1
stack = []
for eachngb in ngb[start]:
  stack.append(eachngb)
  nodes[eachngb][0] = 1
  nodes[eachngb][1] = start


while 1:
  try:
    nownode = stack.pop()
  except:
    break

  if nownode == goal:
    break

  
  
  
  for eachngb in ngb[nownode]:
    if nodes[eachngb][0] == -1:
      stack.append(eachngb)
      
      nodes[eachngb][0] = nodes[nownode][0]+1
      nodes[eachngb][1] = nownode


length = nodes[goal][0] 
FenRootPos = length // 2 
SnRootPos = FenRootPos + 1 
FenRoot = -1 
SnRoot = -1 


nextnode = goal

for i in range(length, FenRootPos-1, -1):
  nownode = nextnode
  if i == SnRootPos:
    SnRoot = nownode
  elif i == FenRootPos:
    FenRoot = nownode
  nextnode = nodes[nownode][1]






ndsFen = [-1] * N
ndsFen[SnRoot] = 0
ndsFen[FenRoot] = 0
stkFen = []
stkFen.append(FenRoot)
FenCnt = 0
while 1:
  try:
    nownode = stkFen.pop()
  except:
    break

  
  
  
  for eachngb in ngb[nownode]:
    if ndsFen[eachngb] == -1:
      stkFen.append(eachngb)
      
      ndsFen[eachngb] = 1
      FenCnt += 1



ndsSn = [-1] * N
ndsSn[FenRoot] = 0
ndsSn[SnRoot] = 0
stkSn = []
stkSn.append(SnRoot)
SnCnt = 0
while 1:
  try:
    nownode = stkSn.pop()
  except:
    break

  
  
  
  for eachngb in ngb[nownode]:
    if ndsSn[eachngb] == -1:
      stkSn.append(eachngb)
      
      ndsSn[eachngb] = 1
      SnCnt += 1

print('Fennec' if FenCnt > SnCnt else 'Snuke')

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

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


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()

N = int(input())

for i in range(N-1):
    u, v = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, 1)
    g.add_edge(v-1, u-1, 1)

d1 = Dijkstra(g, 0)
d2 = Dijkstra(g, N-1)

ans = 0




for i in range(N):
    if d1.dist[i] <= d2.dist[i]:
        ans += 1

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

Solution (Python):
N=int(input())
from collections import defaultdict,deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
check={0}
bef=[-2]*N
bef[0]=-1
dist=[float('inf')]*N
dist[0]=0
while len(check)>0:
    now=check.pop()
    for nex in branch[now]:
        if bef[nex]==-2:
            bef[nex]=now
            check|={nex}
            dist[nex]=dist[now]+1
NG=set()
OK={0}
now=N-1
checked={0}
for i in range((1+dist[N-1])//2):
    NG|={now}
    now=bef[now]
checked|=NG
for i in range(N):
    if i in checked:
        continue
    else:
        visited={i}
        now=i
        while True:
            now=bef[now]
            visited|={now}
            if now in NG:
                NG|=visited
                checked|=visited
                break
            elif now in OK:
                OK|=visited
                checked|=visited
                break
if len(OK)>N//2:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from heapq import heappush, heappop


N = int(input())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)


G = [{} for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x][y] = 1
    G[y][x] = 1
INF = 10**10


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp1 = dijkstra(G, 1)
dpN = dijkstra(G, N)


ans = (
    'Fennec' if sum(dp1[i] <= dpN[i] for i in range(1, N + 1)) > N // 2 else
    'Snuke'
)


print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)


N = int(input())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)

G = [set() for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x].add(y)
    G[y].add(x)


dp = [0 for _ in range(N + 1)]
dp[1] = 1


def f(i):
    for j in G[i]:
        if dp[j] == 0:
            dp[j] = i
            f(j)


f(1)
p = []
i = N
while i != 1:
    p.append(i)
    i = dp[i]
p.append(1)
dp2 = [0 for _ in range(N + 1)]
for j in range(len(p)):
    if dp2[p[-(j + 1)]] == 0:
        dp2[p[-(j + 1)]] = 1
    if dp2[p[j]] == 0:
        dp2[p[j]] = -1
dp3 = [0 for _ in range(N + 1)]
dp3[1] = 1


def g(i):
    for j in G[i]:
        if dp3[j] == 0 and dp2[j] != -1:
            dp3[j] = 1
            g(j)


g(1)
ans = (
    'Fennec' if dp3.count(1) > N // 2 else
    'Snuke'
)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

N=int(input())

B=[[]for i in range(N+1)]

F=[10**10 for i in range(N+1)]
F[1]=0
S=[10**10 for i in range(N+1)]
S[N]=0

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

def dfsF(f):
    for i in B[f]:
        if F[i]==10**10:
            F[i]=F[f]+1
            dfsF(i)
dfsF(1)

def dfsS(s):
    for i in B[s]:
        if S[i]==10**10:
            S[i]=S[s]+1
            dfsS(i)
dfsS(N)


Fennec=0
Snuke=0
for i in range(1,N+1):
    if F[i]<=S[i]:
        Fennec+=1
    else:
        Snuke+=1
if Fennec>Snuke:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

N=int(input())

B=[[]for i in range(N+1)]

F=[10**10 for i in range(N+1)]
F[1]=0
S=[10**10 for i in range(N+1)]
S[N]=0

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

def dfsF(f):
    for i in B[f]:
        if F[i]==10**10:
            F[i]=F[f]+1
            dfsF(i)
dfsF(1)

def dfsS(s):
    for i in B[s]:
        if S[i]==10**10:
            S[i]=S[s]+1
            dfsS(i)
dfsS(N)


Fennec=0
Snuke=0
for i in range(1,N+1):
    if F[i]<=S[i]:
        Fennec+=1
    else:
        Snuke+=1
if Fennec>Snuke:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)
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)
visited = [False for _ in range(N)]
fennec = [-1 for _ in range(N)]
snuke = [-1 for _ in range(N)]
def dfs(start,visited,distance,d):
    visited[start] = True
    d[start] = distance
    for term in edges[start]:
        if visited[term]:
            continue
        dfs(term,visited,distance + 1,d)
dfs(0,visited,0,fennec)

visited = [False for _ in range(N)]
    
dfs(N-1,visited,0,snuke)
F = S = 0
for i in range(N):
    if fennec[i] <= snuke[i]:
        F+=1
    else:
        S+=1
if F>S:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import deque
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)
d = [[-1] * N for _ in range(2)]
for i in range(2):
    d[i][i * (N - 1)] = 0
    q = deque([i * (N - 1)])
    while len(q) > 0:
        u = q.popleft()
        for v in edge[u]:
            if d[i][v] > -1:
                continue
            d[i][v] = d[i][u] + 1
            q.append(v)
S = 0
F = 0
for i in range(N):
    if d[0][i] > d[1][i]:
        S += 1
    else:
        F += 1
if F > S:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import deque
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)
d = [[-1] * N for _ in range(2)]
for i in range(2):
    d[i][i * (N - 1)] = 0
    q = deque([i * (N - 1)])
    while len(q) > 0:
        u = q.popleft()
        for v in edge[u]:
            if d[i][v] > -1:
                continue
            d[i][v] = d[i][u] + 1
            q.append(v)
S = 0
F = 0
for i in range(N):
    if d[0][i] > d[1][i]:
        S += 1
    else:
        F += 1
if F > S:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
n = int(input())
nl = {}
for _ in range(n-1):
  a, b = map(int, input().split())
  if a-1 in nl:
    nl[a-1].append(b-1)
  else:
    nl[a-1] = [b-1]
  if b-1 in nl:
    nl[b-1].append(a-1)
  else:
    nl[b-1] = [a-1]

fenl = [-1 for _ in range(n)]
sunl = [-1 for _ in range(n)]
fenl[0] = 1
sunl[-1] = 1
now = [0]
while now:
  tmp = []
  for _n in now:
    for nxt in nl[_n]:
      if fenl[nxt] == -1:
        tmp.append(nxt)
        fenl[nxt] = fenl[_n] + 1
  now = tmp

now = [n-1]
while now:
  tmp = []
  for _n in now:
    for nxt in nl[_n]:
      if sunl[nxt] == -1:
        tmp.append(nxt)
        sunl[nxt] = sunl[_n] + 1
  now = tmp

fm, sm = 0, 0
for i in range(n):
  if fenl[i] <= sunl[i]:
    fm += 1
  else:
    sm += 1

if fm <= sm:
  print('Snuke')
else:
  print('Fennec')

Solution (Python):
n = int(input())
edges = [[] for _ in range(n)]
 
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
dp = [0]*n
dp[0] =1
fp = [0]*n
fp[n-1] =1
def bfs(u):
    q = []
    q.append(u)
    while q:
        p = q.pop()
        for i in edges[p]:
            if dp[i] ==0 :
                q.append(i)
                dp[i]+=dp[p]+1
def ffs(u):
    q = []
    q.append(u)
    while q:
        p = q.pop()
        for i in edges[p]:
            if fp[i] ==0 :
                q.append(i)
                fp[i]+=fp[p]+1
bfs(0)
ffs(n-1)
c = 0
for i in range(n):
    if dp[i] <= fp[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import deque
n = int(input())
board = [0]*n
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
q = deque()
q.append((0,1))
q.append((-1,-1))
while q:
    from_, color = q.popleft()
    if board[from_] != 0:
        continue
    board[from_] = color
    for i in edge[from_]:
        q.append((i,color))
if sum(board) > 0:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import defaultdict as dd
tree = dd(list)
def dfs_route(tree,start,goal):
    visited = set()
    stack = list()
    visited.add(start)
    stack.append(start)
    while stack:
        node = stack[-1]
        if node == goal:
            return stack
        else:
            child = [x for x in tree[node] if x not in visited]
            if child == []:
                stack.pop()
            else:
                visited.add(child[0])
                stack.append(child[0])
n = int(input())
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
l = dfs_route(tree,1,n)
fl = l[(len(l)-1)//2]
sl = l[(len(l)+1)//2]
tree[fl].remove(sl)
tree[sl].remove(fl)
def gr(tree,start):
    island = set()
    rest = [start,]
    while rest:
        node = rest.pop()
        island.add(node)
        for x in tree[node]:
            if x not in island:
                rest.append(x)
    return(island)
if len(gr(tree,1))*2 > n:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
from heapq import heappop, heappush

N = int(input())
L = [[] for i in range(N + 1)]
Fd = [float("inf") for i in range(N + 1)]
Sd = [float("inf") for i in range(N + 1)]
Fd[1] = 0
Sd[N] = 0

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

Q = []
heappush(Q, 1)
while Q:
    n = heappop(Q)
    d = Fd[n]
    for x in L[n]:
        if Fd[x] == float("inf"):
            Fd[x] = d + 1
            heappush(Q, x)

Q = []
heappush(Q, N)
while Q:
    n = heappop(Q)
    d = Sd[n]
    for x in L[n]:
        if Sd[x] == float("inf"):
            Sd[x] = d + 1
            heappush(Q, x)

f = 0
s = 0
for i in range(1, N + 1):
    if Fd[i] <= Sd[i]:
        f += 1
    else:
        s += 1

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

Solution (Python):
from scipy.sparse import*
n,*a=map(int,open(0).read().split())
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix(([1]*~-n,(a[::2],a[1::2])),[n+1]*2),0,[1,n])))*2>=n::2])

Solution (Python):
from scipy.sparse import*
n,*a=map(int,open(0).read().split())
c=[1]*~-n
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix((c,(a[::2],a[1::2])),[n+1]*2),0,[1,n])))*2>=n::2])

Solution (Python):
from scipy.sparse import*
f=lambda*z:map(int,input().split())
n,=f()
c=[1]*~-n
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix((c,list(zip(*map(f,c)))),[n+1]*2),0,[1,n])))*2>=n::2])

Solution (Python):
from collections import*
input=open(0).readline
n=int(input())
e=[[]for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
f=[0]*n
v=[1]+[0]*~-n
q=deque([(0,0)])
while q:
    t,c=q.pop()
    v[t]=1
    f[t]=c
    for i in e[t]:
        if not v[i]:
            q.append((i,c+1))
s=[0]*n
v=[0]*~-n+[1]
q=deque([(n-1,0)])
while q:
    t,c=q.pop()
    v[t]=1
    s[t]=c
    for i in e[t]:
        if not v[i]:
            q.append((i,c+1))
a=b=0
for i,j in zip(f,s):
    if i<=j:
        a+=1
    else:
        b+=1
if a>b:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from collections import*
input=open(0).readline
n=int(input())
e=[[]for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
f=[0]*n
v=[1]+[0]*~-n
q=deque([(0,0)])
while q:
    t,c=q.pop()
    v[t]=1
    f[t]=c
    for i in e[t]:
        if not v[i]:
            q.append((i,c+1))
s=[0]*n
v=[0]*~-n+[1]
q=deque([(n-1,0)])
while q:
    t,c=q.pop()
    v[t]=1
    s[t]=c
    for i in e[t]:
        if not v[i]:
            q.append((i,c+1))
a=b=0
for i,j in zip(f,s):
    if i<=j:
        a+=1
    else:
        b+=1
if a>b:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
N=int(input())

import sys
sys.setrecursionlimit(10**5)
ab=[list(map(int, input().split())) for _ in range (N-1)]
con=[[] for _ in range(N+1)]


for a,b in ab :
  con[a].append(b)
  con[b].append(a)


pc=[0]*(N+1)
q=[(1,0)]
vis=[False]*(N+1)
vis[1]=True
Fcnt=N
while q:
  n,c=q.pop()
  pc[n]=c
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
q=[(N,0)]
vis=[False]*(N+1)
vis[N]=True
while q:
  n,c=q.pop()
  if pc[n]>c:
    Fcnt-=1
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
if Fcnt>N-Fcnt:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):



import sys


class UnionFind:
    '''
    配列を用いたUnionFind
    '''

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        '''
        xのグループ番号を返す
        '''
        return self.table[x]

    def union(self, val, y):
        '''
        Fennecは0
         SnukeはN-1とすることで、O(1)にする
         '''
        self.table[y] = val

    def same(self, x, y):
        '''
        xとyが同じグループならtrue
        '''
        x1 = self.find(x)
        y1 = self.find(y)
        return x1 == y1

    def get_table(self):
        return self.table



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

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

Un = UnionFind(N)
S = [N-1]
F = [0]
S_or = N-1
F_or = 0


def oneStep(turn):
    ret = []
    if turn == 1:
        while S:
            c = S.pop(0)
            for i in adj[c]:
                if not Un.same(S_or, i) and not Un.same(F_or, i):
                    Un.union(S_or, i)
                    ret.append(i)
    else:
        while F:
            c = F.pop(0)
            for i in adj[c]:
                if not Un.same(S_or, i) and not Un.same(F_or, i):
                    Un.union(F_or, i)
                    ret.append(i)
    return ret


turn = 0
while S or F:
    if turn == 1:
        if len(S) != 0:
            S = oneStep(turn)
        turn = 0
    else:
        if len(F) != 0:
            F = oneStep(turn)
        turn = 1

cntF = Un.get_table().count(0)
cntS = Un.get_table().count(N-1)
if cntF > cntS:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)

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

prev = [-1]*N
def DFS(start):
    res = 0
    for u in G[start]:
        if u != prev[start]:
            prev[u] = start
            res += DFS(u)
    return res+1

DFS(0)
start = N-1
path = [N-1]
while True:
    path.append(prev[start])
    start = prev[start]
    if start == 0:
        break
path.reverse()
num = len(path)
c, d = (path[(num+1)//2-1], path[(num+1)//2])
G[c].remove(d)
G[d].remove(c)
prev = [-1]*N
DFS0 = DFS(0)
prev = [-1]*N
if DFS0 > DFS(N-1):
    print("Fennec")
else:
    print("Snuke")