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:
import sys

import numpy as np

sys.setrecursionlimit(2 ** 31 - 1)
INF = float('inf')

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]

graph = [set() for _ in range(N + 1)]
for a, b in AB:
    graph[a].add(b)
    graph[b].add(a)


def dfs(to, path):
    if path[-1] == to:
        return path
    v = path[-1]
    prev = path[-2] if len(path) >= 2 else None

    ret = None
    for u in graph[v]:
        if u != prev:
            ret = ret or dfs(to, path + [u])
    return ret


# 1 から N までのパス
path = dfs(N, [1])
cut = (len(path) - 1) // 2
fennec = path[:cut + 1]
snuke = path[cut + 1:]

fixed = np.zeros(N + 1, dtype=str)
fixed[fennec] = 'f'
fixed[snuke] = 's'

while fennec:
    v = fennec.pop()
    for u in graph[v]:
        if not fixed[u]:
            fixed[u] = 'f'
            fennec.append(u)
while snuke:
    v = snuke.pop()
    for u in graph[v]:
        if not fixed[u]:
            fixed[u] = 's'
            snuke.append(u)

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

Submission status: Time Limit Exceeded

Solution code:
import sys


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


sys.setrecursionlimit(2 ** 31 - 1)
INF = float('inf')

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]

graph = [set() for _ in range(N + 1)]
for a, b in AB:
    graph[a].add(b)
    graph[b].add(a)


def dfs(to, path):
    if path[-1] == to:
        return path
    v = path[-1]
    prev = path[-2] if len(path) >= 2 else None

    ret = None
    for u in graph[v]:
        if u != prev:
            ret = ret or dfs(to, path + [u])
    return ret


# 1 から N までのパス
path = dfs(N, [1])
cut = (len(path) - 1) // 2
fennec = path[cut]
snuke = path[cut + 1]

uf = UnionFind(size=N + 1)
for a, b in AB:
    if sorted([a, b]) != sorted([fennec, snuke]):
        uf.unite(a, b)

if uf.size(fennec) > uf.size(snuke):
    print('Fennec')
else:
    print('Snuke')

Submission status: Time Limit Exceeded

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

n = int(input())
e = [[] for _ in range(n)]

for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    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 True
    for item in e[start]:
        if item != par:
             if get_path(item, end, start, path + [item]):
                 return True

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 = n - p - 2 
if p > q:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

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

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 True
    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 = n - p - 2 
if p > q:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

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

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 True
    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("Snuke")

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
check=deque([(1,{1,N})])
while len(check)>0:
    now=check.popleft()
    for i in branch[now[0]]:
        if i in now[1]:
            continue
        brack[i]=brack[now[0]]+1
        check.append((i,now[1]|{i,}))
white=[float('inf')]*(N+1)
white[N]=0
check=deque([(N,{N,1}),])
while len(check)>0:
    now=check.popleft()
    for i in branch[now[0]]:
        if i in now[1]:
            continue
        white[i]=white[now[0]]+1
        check.append((i,now[1]|{i,}))
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
check=[(1,{1,}),]
check=deque(check)
while len(check)>0:
    now=check.popleft()
    for i in branch[now[0]]:
        if i in now[1]:
            continue
        if i==N:
            continue
        brack[i]=brack[now[0]]+1
        check.append((i,now[1]|{i,}))
white=[float('inf')]*(N+1)
white[N]=0
check=[(N,{N,}),]
check=deque(check)
while len(check)>0:
    now=check.popleft()
    for i in branch[now[0]]:
        if i in now[1]:
            continue
        if i==1:
            continue
        white[i]=white[now[0]]+1
        check.append((i,now[1]|{i,}))
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import queue
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = queue.Queue()
q.put(0)
d_f[0] = 0
while q:
    x = q.get()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.put(y)
d_s = [-1 for i in range(n)]
q.put(n-1)
d_s[n-1] = 0
while q:
    x = q.get()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.put(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
num_hen = n-1
info = [list(map(int,input().split())) for i in range(num_hen)]

for i in range(num_hen):
  info[i][0] -=1
  info[i][1] -=1

tree=[[] for i in range(n)]
for i in range(num_hen):
  tree[info[i][0]].append(info[i][1])
  tree[info[i][1]].append(info[i][0])
  
#paintedが0のときまだ塗られていない、1のとき黒、-1のとき白
painted=[0]*n
painted[0]=1
painted[n-1]=-1

#0からn-1まで行くための経路を求める（dfsで経路復元する）。
#keiroが経路になる
que = deque()
for i in range(len(tree[0])):
  que.append([tree[0][i],0])
visited=[False]*n 
visited[0]=True
keiro =[]
while que:
  v = que.pop()
  for i in range(len(keiro))[::-1]:
    if keiro[i][1]>=v[1]:
      del keiro[i]
  keiro.append(v)
  if v[0] == n-1:
    del keiro[-1]
    break
  elif not visited[v[0]]:
    for i in range(len(tree[v[0]])):
      que.append([tree[v[0]][i],v[1]+1])
    visited[v[0]]=True

#経路を黒と白で塗る
for i in range(len(keiro)):
  if i%2==0:
    painted[keiro[i//2][0]]=1
  else:
    painted[keiro[len(keiro)-1-i//2][0]]=-1

#全部の頂点に渡ってペイントするためのdfs
def dfs(i,color):
  que2 = deque()
  for element in tree[i]:
    que2.append(element)
  while que2:
    w = que2.pop()
    if painted[w]==0:
      painted[w]=color
      for element in tree[w]:
        que2.append(element)
  return

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

print("Fennec" if painted.count(1) > painted.count(-1) else "Snuke")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
li = []
for _ in range(n - 1):
    li.append(list(map(int, input().split())))

# construct graph
edges = [set() for _ in range(n)]
for i, j in li:
    i -= 1
    j -= 1
    edges[i].update({j})
    edges[j].update({i})

# search middle edge and cut
Q = deque()
Q.append([0])
while len(Q) > 0:
    path = Q.pop()
    if path[-1] == n - 1:
        i = (len(path) - 1) // 2
        a, b = path[i], path[i + 1]
        edges[a].remove(b)
        edges[b].remove(a)
        break
    for v in edges[path[-1]]:
        if v not in path:
            Q.append(path + [v])

# count Fennec's area
Q = deque()
Q.append(0)
visited = {0}
while len(Q) > 0:
    u = Q.pop()
    for v in edges[u]:
        if v not in visited:
            visited.update({v})
            Q.append(v)

ans = 'Snuke' if len(visited) <= n // 2 else 'Fennec'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
li = []
for _ in range(n - 1):
    li.append(list(map(int, input().split())))

# construct graph
edges = [[] for _ in range(n)]
for i, j in li:
    i -= 1
    j -= 1
    edges[i].append(j)
    edges[j].append(i)

# search middle edge and cut
Q = deque()
Q.append([0])
while len(Q) > 0:
    path = Q.pop()
    if path[-1] == n - 1:
        i = (len(path) - 1) // 2
        a, b = path[i], path[i + 1]
        edges[a].remove(b)
        edges[b].remove(a)
        break
    for v in edges[path[-1]]:
        if v not in path:
            Q.append(path + [v])

# count Fennec's area
Q = deque()
Q.append(0)
visited = {0}
while len(Q) > 0:
    u = Q.pop()
    for v in edges[u]:
        if v not in visited:
            visited.update({v})
            Q.append(v)

ans = 'Snuke' if len(visited) <= n // 2 else 'Fennec'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#067-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n=I()
prev=[-1 for i in range(n)]
nl=[[] for i in range(n)]
q=[0]
vis=[False for i in range(n)]

for i in range(n-1):
    a,b=IL()
    nl[a-1].append(b-1)
    nl[b-1].append(a-1)

while len(q)!=0:
    s=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            prev[v]=s
            q.append(v)

path=[n-1]
while True:
    if path[-1]==0:
        break
    path.append(prev[path[-1]])
path.reverse()
    
for i in range(1,n):
    while True:
        if prev[i] in path:
            break
        prev[i]=prev[prev[i]]

if len(path)%2==0:
    fenp=path[:len(path)//2]
    fen=len(path)//2
else:
    fenp=path[:len(path)//2+1]
    fen=len(path)//2+1

snu=len(path)-fen

r=list(range(n))
for i in path:
    r.remove(i)
for i in r:
    if prev[i] in fenp:
        fen+=1
    else:
        snu+=1

        
if fen>snu:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
#067-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n=I()
prev=[-1 for i in range(n)]
nl=[[] for i in range(n)]
q=[0]
vis=[False for i in range(n)]

for i in range(n-1):
    a,b=IL()
    nl[a-1].append(b-1)
    nl[b-1].append(a-1)

while len(q)!=0:
    s=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            prev[v]=s
            q.append(v)

path=[n-1]
while True:
    if path[-1]==0:
        break
    path.append(prev[path[-1]])
path.reverse()
    
for i in range(1,n):
    while True:
        if prev[i] in path:
            break
        prev[i]=prev[prev[i]]

if len(path)%2==0:
    fenp=path[:len(path)//2]
    fen=len(path)//2
else:
    fenp=path[:len(path)//2+1]
    fen=len(path)//2+1

snu=len(path)-fen

for i in range(n):
    if i not in path:
        if prev[i] in fenp:
            fen+=1
        else:
            snu+=1
    
if fen>snu:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
#067-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n=I()
prev=[-1 for i in range(n)]
nl=[[] for i in range(n)]
q=[0]
vis=[False for i in range(n)]

for i in range(n-1):
    a,b=IL()
    nl[a-1].append(b-1)
    nl[b-1].append(a-1)

def bfs(s):
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            prev[v]=s
            q.append(v)
    return

while len(q)!=0:
    s=q.pop(0)
    bfs(s)

path=[n-1]
while True:
    if path[-1]==0:
        break
    path.append(prev[path[-1]])
path.reverse()
    
for i in range(1,n):
    while True:
        if prev[i] in path:
            break
        prev[i]=prev[prev[i]]

if len(path)%2==0:
    fenp=path[:len(path)//2]
    fen=len(path)//2
else:
    fenp=path[:len(path)//2+1]
    fen=len(path)//2+1

snu=len(path)-fen

for i in range(n):
    if i not in path:
        if prev[i] in fenp:
            fen+=1
        else:
            snu+=1
    
if fen>snu:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


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

path = Dijkstra(graph, 0, N - 1).execute()
cost = len(path) - 1

black = 1
if cost % 2 == 0:
    tmp = (cost - 1) // 2
    black += tmp + 1
else:
    tmp = (cost - 1) // 2
    black += tmp
not_path = set(path[black:])
visited = [False for _ in range(N)]
q = [0]
visited[0] = False
while len(q) != 0:
    dist = q.pop()
    for d in graph[dist].keys():
        if visited[d] or d in not_path:
            continue
        q.append(d)
        visited[d] = True

for i, v in enumerate(visited):
    if v and i not in path:
        black += 1
white = N - black

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
edge=[]
adj=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  edge.append([a,b])
  adj[a].append(b)
  adj[b].append(a)
pathget=[[-1,0] for i in range(N)]
deque=[0]
check=0
while check==0:
  t=deque.pop()
  if N-1 in adj[t]:
    pathget[N-1][0]=t
    pathget[N-1][1]=pathget[t][1]+1
    check=1
    continue
  for p in adj[t]:
    deque.append(p)
    if pathget[p][0]<0:
      pathget[p][0]=t
      pathget[p][1]=pathget[t][1]+1
    
j=N-1
tr=pathget[N-1][1]//2-1
for i in range(tr):
  j=pathget[j][0]
k=pathget[j][0]
if [j,k] in edge:
  edge.remove([j,k])
else:
  edge.remove([k,j])
Tree=[i for i in range(N)]
size=[1]*N
 
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
    size[s1]+=size[s2]
for e,f in edge:
  unite(e,f)
  
if size[Tree[0]]>N//2:
  print("Fennec")
else:
  print("Snuke")

Submission status: Time Limit Exceeded

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 += g[node]

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

Solution code:
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
root=[[0]]
depth=[-1]*N
depth[0]=0
while root:
  R=root.pop()
  s=R[-1]
  if s==N-1:
    one_to_N=R
    break
  for t in graph[s]:
    if depth[t]==-1:
      depth[t]=depth[s]+1
      root.append(R+[t])
d=len(one_to_N)
if d%2==1:
  a,b=one_to_N[d//2],one_to_N[d//2+1]
else:
  a,b=one_to_N[d//2-1],one_to_N[d//2]
graph[a].remove(b)
graph[b].remove(a)

dfs_stack=[0]
tree=[0]
depth1=[-1]*N
depth1[0]=0
while dfs_stack:
  s1=dfs_stack.pop()
  for t1 in graph[s1]:
    if depth1[t1]==-1:
      depth1[t1]=1
      dfs_stack.append(t1)
      tree.append(t1)
  
F=len(tree)

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

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict
import queue


def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 
 
 
N = int(input())
 
# Y,P,i
adj = {}
 
for i in range(N):
	adj[i] = []
 
 
for i in range(N-1):
	a, b = list(map(int, input().split(' ')))
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
 
def bfs(s):
    dist = defaultdict(lambda:float('inf'))
    dist[s] = 0
    que = queue.Queue()
    que.put(s)
    while que.qsize():
        s = que.get()
        for t in adj[s]:
            if dist[t] > dist[s] + 1:
                dist[t] = dist[s] + 1
                que.put(t)
    return dist
 
length_from_1 = bfs(0)
length_from_N = bfs(N-1)
 
# [0, 1, 1, 1, 3, 2, 2]
# [2, 3, 3, 1, 1, 4, 0]
 
snuke = 0
fennec = 0
for i in range(N):
	if(length_from_1[i] <= length_from_N[i]):
		fennec +=1
	else:
		snuke +=1
 
if(fennec>snuke):
	print("Fennec")
else:
	print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [input().rstrip().split() for j in range(n-1)]
graph = [[False for i in range(n)] for j in range(n)]#どこが連結されているか
# graph
for i in range(0,n-1):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=True
# graph
d1 = [0]*n#かかった距離
d2 =[0]*n
def DFS(v,visited,cnt,d):
    all_visited = True #bool
    for i in range(0,n):
        if(visited[i]==False):
            all_visited = False
    if(all_visited):
        return 
    visited[v]=True
    for i in range(0,n):
        if(graph[v][i]==False):
            continue
        if(visited[i]):
            continue
        cnt += 1
        d[i]=cnt
        DFS(i,visited,cnt,d)
        cnt -= 1
    return


visited=[False]*n
visited[0]=True
DFS(0,visited,0,d1)
visited=[False]*n
visited[n-1]=True
DFS(n-1,visited,0,d2)
# d1
# d2
white=0
black=0
for i in range(1,n-1):
    if d1[i]<=d2[i]:
        black+=1
    else:
        white+=1
if black>white:
    print('Fennec')
if black<=white:
    print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [input().rstrip().split() for j in range(n-1)]
graph = [[False for i in range(n)] for j in range(n)]#どこが連結されているか
# graph
for i in range(0,n-1):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=True
# graph
d1 = [0]*n#かかった距離
d2 =[0]*n
def DFS(v,visited,cnt,d):
    all_visited = True #bool
    for i in range(0,n):
        if(visited[i]==False):
            all_visited = False
    if(all_visited):
        return 
    visited[v]=True
    for i in range(0,n):
        if(graph[v][i]==False):
            continue
        if(visited[i]):
            continue
        cnt += 1
        d[i]=cnt
        DFS(i,visited,cnt,d)
        cnt -= 1
    return


visited=[False]*n
visited[0]=True
DFS(0,visited,0,d1)
visited=[False]*n
visited[n-1]=True
DFS(n-1,visited,0,d2)
d1
d2
white=0
black=0
for i in range(1,n-1):
    if d1[i]<=d2[i]:
        black+=1
    else:
        white+=1
if black>white:
    print('Fennec')
if black<=white:
    print('Snuke')

Submission status: Time Limit Exceeded

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

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


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

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

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

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


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


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

Submission status: Time Limit Exceeded

Solution code:
import queue
inf = float('inf')
N = int(input())
paths = [{} for i in range(N+1)]
for i in range(N-1):
    s,t = list(map(int, input().split()))
    paths[s][t] = 1
    paths[t][s] = 1

def dijkstra(start, nodes, N):
    fixed = {}
    cost = [inf] * (N + 1)
    cost[start] = 0
    q = queue.PriorityQueue()
    q.put((0, start))
    while q.empty() == False:
        w, x = q.get()
        if cost[x] < w: continue
        for y in nodes[x]:
            if cost[x] + paths[x][y] < cost[y]:
                cost[y] = cost[x] + paths[x][y]
                q.put((cost[y], y))
    return cost

# それぞれの位置からの到達コストを調べている
score_f = dijkstra(1, paths, N)
score_s = dijkstra(N, paths, N)

score = 0
for i in range(1, N+1):
    if score_f[i] > score_s[i]:
        score -= 1
    else:
        score += 1

if score > 0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

inf = float('inf')

import heapq
def dijkstra(adj, n, st=1):
    dj = [inf] * (n + 1)
    paths = dict((x, [x]) for x in range(n + 1))
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                paths[tn] = paths[fn] + [tn]
                heapq.heappush(q, (dj[tn], tn))
    return dj, paths

import itertools
def reachable(adj, st):
    reached = set([st])
    cur = set([st])
    while cur:
        nxt = set(itertools.chain(*[[y[0] for y in adj[x]] for x in cur]))
        reached.update(cur)
        cur = nxt - reached
    return reached

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

costs, paths = dijkstra(adj, N, 1)
main_street = paths[N]
import math
mid = math.ceil(len(main_street) / 2) - 1
mid_v0 = main_street[mid]
mid_v1 = main_street[mid + 1]
adj[mid_v0] = filter(lambda x: x[0] != mid_v1, adj[mid_v0])
adj[mid_v1] = filter(lambda x: x[0] != mid_v0, adj[mid_v1])

fennec = len(reachable(adj, 1))
snuke = N - fennec

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

inf = float('inf')

import heapq
def dijkstra(adj, n, st=1):
    dj = [inf] * (n + 1)
    paths = dict((x, [x]) for x in range(n + 1))
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                paths[tn] = paths[fn] + [tn]
                heapq.heappush(q, (dj[tn], tn))
    return dj, paths

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

costs, paths = dijkstra(adj, N, 1)
main_street = paths[N]
import math
mid = math.ceil(len(main_street) / 2) - 1
mid_v0 = main_street[mid]
mid_v1 = main_street[mid + 1]
adj[mid_v0] = filter(lambda x: x[0] != mid_v1, adj[mid_v0])
adj[mid_v1] = filter(lambda x: x[0] != mid_v0, adj[mid_v1])

fennec = N - dijkstra(adj, N, 1)[0].count(inf) + 1
snuke = N - fennec

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