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: Time Limit Exceeded

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def calc_dist_path_in_bfs(adj, start, goal):
        q = deque()
        q.append([[start], 0])
        while q:
            path, dist = q.popleft()
            u = path[-1]
            if u == goal:
                return dist, path
            if not visited[u]:
                visited[u] = True
                for v in adj[u]:
                    if not visited[v]:
                        tmp = path[:]
                        tmp.append(v)
                        q.append([tmp, dist+1])
    
    def calc_node_in_dfs(adj, start):
        cnt = 1
        stack = [start]
        visited[start] = True
        while stack:
            # print(stack)
            u = stack[-1]
            for v in adj[u]:
                if not visited[v]:
                    stack.append(v)
                    visited[v] = True
                    cnt += 1                  
                    break
            else:
                stack.pop()
        return cnt


    n = ii()
    adj = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = mi_0()
        adj[a].append(b)
        adj[b].append(a)
    
    visited = [False] * n
    dist, path = calc_dist_path_in_bfs(adj, start=0, goal=n-1)
    # print(dist)
    # print(path)
    
    visited = [False] * n
    if dist % 2 == 1:
        i = path[(dist-1)//2]
        j = path[(dist-1)//2 + 1]
        adj[i].remove(j)
        adj[j].remove(i)
        # i 彩色数 > j 彩色数 で Fennec 勝ち
        i_color = calc_node_in_dfs(adj, i)
        j_color = calc_node_in_dfs(adj, j)
        print('Fennec') if i_color > j_color else print('Snuke')
    else:
        i = path[dist//2]
        j = path[dist//2+1]
        adj[i].remove(j)
        adj[j].remove(i)
        # i 彩色数 >= j 彩色数 で Fennec 勝ち
        i_color = calc_node_in_dfs(adj, i)
        j_color = calc_node_in_dfs(adj, j)
        print('Fennec') if i_color >= j_color else print('Snuke')


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
    
def main():
    N = int(input())
    d = {}
    for _ in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    v = set()
    v.add(1)
    def dfs(n):
        if n == N:
            return True, [N]
        for i in d[n]:
            if i not in v:
                v.add(i)
                t, l = dfs(i)
                if t:
                    return True, l + [n]
        return False, n
    _, l = dfs(1)
    l.reverse()
    v = set()
    if len(l) % 2 == 0:
        half = len(l) // 2 - 1
    else:
        half = len(l) // 2
    v.add(l[half])
    s = l[half+1]
    v.add(s)
    def dfs2(n):
        r = 1
        for i in d[n]:
            if i not in v:
                v.add(i)
                r += dfs2(i)
        return r
    x = dfs2(s)
    if N - x > x:
        return 'Fennec'
    else:
        return 'Snuke'
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
    
def main():
    N = int(input())
    d = {}
    for _ in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    v = set()
    v.add(1)
    def dfs(n):
        if n == N:
            return True, [N]
        for i in d[n]:
            if i not in v:
                v.add(i)
                t, l = dfs(i)
                if t:
                    return True, [n] + l
        return False, n
    _, l = dfs(1)
    v = set()
    if len(l) % 2 == 0:
        half = len(l) // 2 - 1
    else:
        half = len(l) // 2
    v.add(l[half])
    s = l[half+1]
    v.add(s)
    def dfs2(n):
        r = 1
        for i in d[n]:
            if i not in v:
                v.add(i)
                r += dfs2(i)
        return r
    x = dfs2(s)
    if N - x > x:
        return 'Fennec'
    else:
        return 'Snuke'
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from collections import deque
N=int(input())

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

def dfs_init(u,ls):
  global path
  visited[u]=True  
  if u==N:
    path=ls
    return
  
  for v in graph[u]:
    if not visited[v]:
      dfs_init(v,ls+[v])
  
path=[]  
visited=[False]*(N+1)
dfs_init(1,[1])
#print(path)

visited=[False]*(N+1)
set_f=set()
set_s=set()
turn=1
dq=deque(path)
while dq:
  #Fenec
  node_f=dq.popleft()
  visited[node_f]=True
  set_f.add(node_f)
  turn=-1
  
  if dq:
    #Snuke
    node_s=dq.pop()
    visited[node_s]=True
    set_s.add(node_s)
    turn=1
#print(set_f,set_s,visited,turn)

def dfs_fenec(u):
  global cnt_f
  if not visited[u]:
    visited[u]=True
    cnt_f+=1
  for v in graph[u]:
    if not visited[v]:
      dfs_fenec(v)

def dfs_snuke(u):
  global cnt_s
  if not visited[u]:
    visited[u]=True
    cnt_s+=1
  for v in graph[u]:
    if not visited[v]:
      dfs_snuke(v)
      
#fenec
cnt_f=0
for f in set_f:
  dfs_fenec(f)
  
#snuke
cnt_s=0
for s in set_s:
  dfs_snuke(s)
  
#print(cnt_f,cnt_s)
if turn==1:
  if cnt_f>cnt_s:
    print("Fennec")
  else:
    print("Snuke")
elif turn==-1:
  if cnt_f>=cnt_s:
    print("Fennec")
  else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# cook your dish here
def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

################################
n = int(input())#n:頂点数　w:辺の数
w = n-1

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    z=1
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z

short_path = dijkstra_back(0,n-1,n,w,cost)
x_spl= short_path[(len(short_path)-1)//2]
y_spl = short_path[(len(short_path)-1)//2+1]

cost[x_spl][y_spl] = float('inf')
cost[y_spl][x_spl] = float('inf')

from scipy.sparse.csgraph import connected_components

cos = np.array(cost)

n_, labels = connected_components(cos)

f_cout=0
s_cout=0
for i in range(n):
    if labels[i] == 0:
        f_cout+=1
    else:
        s_cout+=1
        
if f_cout>s_cout:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n = int(input())
d = [[float("inf")]*n for i in range(n)]

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
visited0 = [0]*n

@lru_cache(None)
def dfs0(v, parent = -1):
    if dist0[v] == INF:
        dist0[v] = dist0[parent]+1
    for next_v in es[v]:
        if dist0[next_v] == INF:
            dfs0(next_v,v)
dfs0(0)

distn = [INF] * n
distn[n-1] = 0
visitedn = [0]*n

@lru_cache(None)
def dfsn(v, parent = -1):
    if distn[v] == INF:
        distn[v] = distn[parent]+1
    for next_v in es[v]:
        if distn[next_v] == INF:
            dfsn(next_v,v)
dfsn(n-1)

count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = [[float("inf")]*n for i in range(n)]

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
visited0 = [0]*n
def dfs0(v, parent = -1):
    if dist0[v] == INF:
        dist0[v] = dist0[parent]+1
    for next_v in es[v]:
        if dist0[next_v] == INF:
            dfs0(next_v,v)
dfs0(0)

distn = [INF] * n
distn[n-1] = 0
visitedn = [0]*n
def dfsn(v, parent = -1):
    if distn[v] == INF:
        distn[v] = distn[parent]+1
    for next_v in es[v]:
        if distn[next_v] == INF:
            dfsn(next_v,v)
dfsn(n-1)

count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = [[float("inf")]*n for i in range(n)]

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
import heapq
hq = [(0,0)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= dist0[to]: continue
        dist0[to] = c+1
        heapq.heappush(hq,(c+1,to))

distn = [INF] * n
distn[n-1] = 0
hq = [(0,n-1)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= distn[to]: continue
        distn[to] = c+1
        heapq.heappush(hq,(c+1,to))


count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(dp):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])
    return dp

n = int(input())
d = [[float("inf")]*n for i in range(n)]

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

for i in range(n):
    d[i][i] = 0

d= warshall_floyd(d)

count_f = 0
for i in range(n):
    if d[0][i] <= d[n-1][i]:
        count_f+=1


if count_f > n-count_f: print('Fennec')
else: print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def members(self, x):  # 計算量n
        root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == root]

    def all_roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.all_roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.all_roots()}

    def __str__(self):
        return ''.join('{}: {}'.format(r, self.members(r)) for r in self.all_roots())

n = int(input())
uf = UnionFind(n)

ab = [tuple(map(int,input().split())) for i in range(n-1)]
cost = [[float("inf") for i in range(n)] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    cost[a][b]=1
    cost[b][a]=1

# cook your dish here
def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for i in range(n):
            if d[i] > d[v] + cost[v][i]:
                d[i] = d[v] + cost[v][i]
                prev[i] = v

    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

route = dijkstra_back(0,n-1,n,n-1,cost)

mid = route[-(-len(route)//2)-1]
mid_next = route[-(-len(route)//2)]


for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    if a == mid and b == mid_next:continue
    if a == mid_next and b == mid:continue

    uf.union(a,b)

if uf.size(0) > uf.size(n-1):
    print('Fennec')
else:
    print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import Deque, List
except ImportError:
    pass


sys.setrecursionlimit(10000000)


def dfs(G: "List[List[int]]", a: int, b: int, par: int = -1):
    for t in G[a]:
        if t == par:
            continue
        if t == b:
            return [t]
        path = dfs(G, t, b, a)
        if path:
            return [t] + path
    return None


def bfs(G: "List[List[int]]", a: int, par: int = -1):
    q = deque()  # type: Deque[int]
    q.append(a)
    visited = {par, a}
    while q:
        s = q.popleft()
        for t in G[s]:
            if t in visited:
                continue
            q.append(t)
            visited.add(t)
    return len(visited) - 1


def solve(N: int, a: "List[int]", b: "List[int]"):
    G = [[] for i in range(N)]
    for ai, bi in zip(a, b):
        ai -= 1
        bi -= 1
        G[ai].append(bi)
        G[bi].append(ai)
    path = dfs(G, 0, N - 1)
    assert path
    path = [0] + path
    bb = path[(len(path) - 1) // 2]
    wb = path[(len(path) + 1) // 2]
    bn = bfs(G, bb, wb)
    wn = bfs(G, wb, bb)
    if bn > wn:
        print("Fennec")
    else:
        print("Snuke")


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: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**6)

def killme(num,lis):
    visited[num]=1
    if num==N-1:
        lis.append(num)
        for index,item in enumerate(lis):
            highway[item]=index
    else:
        for next_n in way[num]:
            if visited[next_n]==0:
                killme(next_n,lis+[num])
    return 

def dfs(num,root):
    visited[num]=1
    cluster[root].append(num)
    for next_n in way[num]:
        if visited[next_n]==0 and highway[next_n]==-1:
            #print(next_n,root)
            dfs(next_n,root)
    return 

N=int(input())

way=[[] for i in range(N)]
visited=[0]*N
highway=[-1]*N

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

killme(0,[])

#print(way)
#print(visited)
#print(highway)

visited=[0]*N
cluster=[[] for i in range(highway[-1]+1)]

for index,item in enumerate(highway):
    if item!=-1:
        dfs(index,item)

F=0
S=0
for i in range(highway[-1]+1):
    if i<=highway[-1]//2:
        F+=len(cluster[i])
    else:
        S+=len(cluster[i])

if F>S:
    print("Fennec")
else:
    print("Snuke")
#print(F,S)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


N = int(input())
G = [[] for _ 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)
visited = [False] * N
visited[0] = True


def dfs(v):
    if v == N-1:
        return [N-1]
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = True
        ret = dfs(u)
        visited[u] = False
        if ret:
            return [v] + ret
    return None


path = dfs(0)
l = len(path)
u, v = 0, 0
if l % 2 == 0:
    u = path[l//2-1]
    v = path[l//2]
else:
    u = path[l//2]
    v = path[l//2+1]
G[u].remove(v)
G[v].remove(u)


def dfs2(v):
    global fen
    fen += 1
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = True
        dfs2(u)
        visited[u] = False


fen = 0
dfs2(0)
if fen > N // 2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
G = [set() for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].add(b)
    G[b].add(a)
visited = [False] * N
visited[0] = True


def dfs(v):
    if v == N-1:
        return [N-1]
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = True
        ret = dfs(u)
        visited[u] = False
        if ret:
            return [v] + ret
    return None


path = dfs(0)
l = len(path)
u, v = 0, 0
if l % 2 == 0:
    u = path[l//2-1]
    v = path[l//2]
else:
    u = path[l//2]
    v = path[l//2+1]
G[u].remove(v)
G[v].remove(u)

uf = UnionFind(N)
for u in range(N):
    for v in G[u]:
        uf.unite(u, v)
fen = 0
snu = 0
for v in range(N):
    if uf.same(v, 0):
        fen += 1
    else:
        snu += 1
if fen > snu:
    print('Fennec')
else:
    print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

# n,w = map(int,input().split()) #n:頂点数　w:辺の数
n = int(input()) #n:頂点数　w:辺の数
w = n - 1

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    cost[x][y] = 1
    cost[y][x] = 1

d0 = dijkstra(0,  n,w,cost)
d1 = dijkstra(n-1,n,w,cost)

f = 0
s = 0
for i in range(1,n-1):
    if d0[i] <= d1[i]:
        f +=1
    else:
        s += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
from scipy.sparse.csgraph import dijkstra

def main():
    N = int(input())
    INF = float('inf')
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        x,y = map(int,input().split())
        dist[x-1][y-1] = 1
        dist[y-1][x-1] = 1
        
    fen = dijkstra(dist,indices = 0)
    snu = dijkstra(dist,indices = N-1)
    fg = sg = 0
    for i in range(N):
        if fen[i] <= snu[i]:
            fg += 1
        else:
            sg += 1
            
    print("Fennec" if fg > sg else "Snuke")
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def find_path(u=0, pu=-1):
        res = []
        if u == n - 1: res = [n - 1]
        for cu in to[u]:
            if cu == pu: continue
            ret = find_path(cu, u)
            if ret:
                res = ret + [u]
            else:
                score[u] += score[cu]
        return res

    n = int(input())
    to = defaultdict(list)
    for _ in range(n - 1):
        a, b = MI()
        a, b = a - 1, b - 1
        to[a].append(b)
        to[b].append(a)
    # 1からＮへのパスを見つける
    score = [1] * n
    path = find_path()
    #print(path)
    #print(score)
    path_n = len(path)
    s_score =sum(score[u] for u in path[:path_n//2])
    f_score =sum(score[u] for u in path[path_n//2:])
    # print(f_score, s_score)
    if f_score > s_score:
        print("Fennec")
    else:
        print("Snuke")

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def find_path(u=0, pu=-1):
        res = []
        if u == n - 1: res = [n - 1]
        for cu in to[u]:
            if cu == pu: continue
            ret = find_path(cu, u)
            if ret:
                res = ret + [u]
            else:
                score[u] += score[cu]
        return res

    n = int(input())
    to = defaultdict(list)
    for _ in range(n - 1):
        a, b = MI()
        a, b = a - 1, b - 1
        to[a].append(b)
        to[b].append(a)
    # 1からＮへのパスを見つける
    score = [1] * n
    path = find_path()
    #print(path)
    #print(score)
    path_n = len(path)
    f_score = s_score = 0
    for i in range(path_n // 2):
        s_score += score[path[i]]
    for i in range(path_n // 2, path_n):
        f_score += score[path[i]]
    # print(f_score, s_score)
    if f_score > s_score:
        print("Fennec")
    else:
        print("Snuke")

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def find_path(u=0, pu=-1):
        if u == n - 1: return [n - 1]
        res = []
        for cu in to[u]:
            if cu == pu: continue
            res += find_path(cu, u)
            if res: return res + [u]
        return res

    def getscore(u, ng, pu=-1):
        res = 1
        for cu in to[u]:
            if cu == ng or cu == pu: continue
            res += getscore(cu, ng, u)
        return res

    n = int(input())
    to = defaultdict(list)
    for _ in range(n - 1):
        a, b = MI()
        a, b = a - 1, b - 1
        to[a].append(b)
        to[b].append(a)
    # 1からＮへのパスを見つける
    path = find_path()
    #print(find_path())
    score = [0] * n
    for i, u in enumerate(path):
        if u == n - 1:
            score[u] = getscore(u, path[i + 1]) - 1
        elif u == 0:
            score[u] = getscore(u, path[i - 1]) - 1
        else:
            score[u] = getscore(u, path[i - 1], path[i + 1])
    #print(score)
    path_n = len(path)
    f_score = s_score = 0
    for i in range(path_n // 2):
        s_score += score[path[i]]
    for i in range(path_n // 2, path_n):
        f_score += score[path[i]]
    #print(f_score, s_score)
    if f_score > s_score:
        print("Fennec")
    else:
        print("Snuke")

main()

Submission status: Time Limit Exceeded

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

stack=[]

import copy

stack.append([0,[],-1])
Nhalf=None
while stack:
  node=stack.pop()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    route.append(v)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
    E[Nhalf].remove(NhalfNext)
    E[NhalfNext].remove(Nhalf)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    stack.append([child,newroute,v])
  del route

stack=[]
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
if count>N-count:
  print("Fennec")
else:
  print("Snuke")

Submission status: Time Limit Exceeded

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

stack=[]

import copy

stack.append([0,[],-1])
Nhalf=None
while stack:
  node=stack.pop()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    route.append(v)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
    E[Nhalf].remove(NhalfNext)
    E[NhalfNext].remove(Nhalf)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    stack.append([child,newroute,v])

stack=[]
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
if count>N-count:
  print("Fennec")
else:
  print("Snuke")