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
sys.setrecursionlimit(10 ** 6)

def main():
    n = int(input())
    adj_list = [[] for i in range(n)]
    for i in range(n - 1):
        a1, b1 = map(int, input().split())
        adj_list[a1 - 1].append(b1 - 1)
        adj_list[b1 - 1].append(a1 - 1)
    path = dfs(0, -1, adj_list, n)
    assert len(path) >= 2
    fpath = len(path) - len(path) // 2
    cut = set(path[fpath - 1:fpath + 1])
    f = dfs2(0, -1, adj_list, n, cut)
    s = dfs2(n - 1, -1, adj_list, n, cut)
    assert f + s == n
    print("Fennec" if f > s else "Snuke")

def dfs(now, prev, adj_list, n):
    if now == n - 1:
        return [now]
    for next in adj_list[now]:
        if next == prev:
            continue
        p = dfs(next, now, adj_list, n)
        if p is not None:
            return [now] + p

def dfs2(now, prev, adj_list, n, cut):
    size = 1
    for next in adj_list[now]:
        if next == prev:
            continue
        if {now, next} == cut:
            continue
        s = dfs2(next, now, adj_list, n, cut)
        size += s
    return size

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    n = int(input())
    adj_list = [[] for i in range(n)]
    for i in range(n - 1):
        a1, b1 = map(int, input().split())
        adj_list[a1 - 1].append(b1 - 1)
        adj_list[b1 - 1].append(a1 - 1)
    path = dfs(0, -1, adj_list, n)
    assert len(path) >= 2
    fpath = len(path) - len(path) // 2
    cut = path[fpath - 1:fpath + 1]
    f = dfs2(0, -1, adj_list, n, cut)
    s = dfs2(n - 1, -1, adj_list, n, cut)
    assert f + s == n
    print("Fennec" if f > s else "Snuke")

def dfs(now, prev, adj_list, n):
    if now == n - 1:
        return [now]
    for next in adj_list[now]:
        if next == prev:
            continue
        p = dfs(next, now, adj_list, n)
        if p is not None:
            return [now] + p

def dfs2(now, prev, adj_list, n, cut):
    size = 1
    for next in adj_list[now]:
        if next == prev:
            continue
        if {now, next} == set(cut):
            continue
        s = dfs2(next, now, adj_list, n, cut)
        size += s
    return size

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([[0,[0]]])
v=[0]*n
v[0]=1
f=0
while q:
    p=q.popleft()
    #if p[1][-1]==n-1:
        #break
    v[p[0]]=1
    for i in g[p[0]]:
        if v[i]==0:
            v[i]=1
            #print(i)
            if i==n-1:
                r=p[1]+[i]
                f=1
                break
            q.append([i,p[1]+[i]])
    if f==1:
        break
fe=deque(r[:(-(-len(r)//2))])
v=[0]*n
v[r[(-(-len(r)//2))]]=1
for i in fe:
    v[i]=1
while fe:
    s=fe.popleft()
    for i in g[s]:
        if v[i]==0:
            fe.append(i)
            v[i]=1
x=sum(v)-1
y=n-x
if x>y:
    print('Fennec')
else:
    print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([[0,[0]]])
v=[0]*n
v[0]=1
f=0
while q:
    p=q.popleft()
    #if p[1][-1]==n-1:
        #break
    v[p[0]]=1
    for i in g[p[0]]:
        if v[i]==0:
            v[i]=1
            #print(i)
            if i==n-1:
                r=p[1]+[i]
                f=1
                break
            q.append([i,p[1]+[i]])
    if f==1:
        break
fe=deque(r[:(-(-len(r)//2))])
v=[0]*n
v[r[(-(-len(r)//2))]]=1
v[0]=1
while fe:
    s=fe.popleft()
    for i in g[s]:
        if v[i]==0:
            fe.append(i)
            v[i]=1
x=sum(v)-1
y=n-x
if x>y:
    print('Fennec')
else:
    print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([[0,[0]]])
v=[0]*n
v[0]=1
f=0
while q:
    p=q.popleft()
    #if p[1][-1]==n-1:
        #break
    v[p[0]]=1
    for i in g[p[0]]:
        if v[i]==0:
            v[i]=1
            #print(i)
            if i==n-1:
                r=p[1]+[i]
                f=1
                break
            q.append([i,p[1]+[i]])
    if f==1:
        break
fe=deque(r[:(-(-len(r)//2))])
v=[0]*n
v[r[(-(-len(r)//2))]]=1
v[0]=1
while fe:
    s=fe.popleft()
    for i in g[s]:
        if v[i]==0:
            fe.append(i)
            v[i]=1
x=sum(v)-1
y=n-x
if x>y:
    print('Fennec')
else:
    print('Snuke')

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10000000)

def solve():
    N = int(input())
    adj = [list() 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)

    # path
    goal = N-1
    def rec(prev, cur):
        if cur == goal:
            return [cur]
        for n in adj[cur]:
            if n != prev:
                res = rec(cur,n)
                if res:
                    return res + [cur]
        return None

    path = rec(None, 0)
    path.reverse()
    black = path[(len(path)-1)//2]
    white = path[(len(path)-1)//2+1]

    # count
    def rec(prev, cur):
        return sum(rec(cur, n) for n in adj[cur] if n != prev) + 1

    bscore = rec(white,black)
    print('Fennec' if bscore*2 > N else 'Snuke')

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10000000)

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

# path
goal = N-1
def rec(prev, cur):
    if cur == goal:
        return [cur]
    for n in adj[cur]:
        if n != prev:
            res = rec(cur,n)
            if res:
                return res + [cur]
    return None

path = rec(None, 0)
path.reverse()
black = path[(len(path)-1)//2]
white = path[(len(path)-1)//2+1]

# count
cnt = 0
def rec(prev, cur):
    return sum(rec(cur, n) for n in adj[cur] if n != prev) + 1

bscore = rec(white,black)
print('Fennec' if bscore*2 > N else 'Snuke')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not x==y: # 根が同じでない場合のみ併合する
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] # 要素数を併合
                self.par[x] = y # 根を付け替えている
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
        
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y) 

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    from collections import defaultdict
    G = defaultdict(list)
    D = []
    for i in range(N-1):
        a, b = map(int,input().split())
        D.append([a,b])
        G[a].append(b)
        G[b].append(a)
    
    from collections import deque
    que = deque()
    que.append([1,[1]])
    visited = {}
    
    while que != deque():
        v = que.pop()
        visited[v[0]] = 1
        if v[0] == N:
            path = v[1]
            break
        else:
            for i in G[v[0]]:
                if not i in visited:
                    que.append([i,v[1]+[i]])
    
    L = len(path)
    if L%2==0:
        d1,d2 = path[L//2-1],path[L//2]
    else:
        d1,d2 = path[L//2],path[L//2+1]
    G2 = UnionFind(N)
    
    for i in D:
        a,b = i
        if not {a,b} == {d1,d2}:
            G2.union(a,b)
    one = -G2.par[G2.find(1)]
    enu = -G2.par[G2.find(N)]
    
    if one>enu:
        print("Fennec")
    else:
        print("Snuke")
    

main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not x==y: # 根が同じでない場合のみ併合する
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] # 要素数を併合
                self.par[x] = y # 根を付け替えている
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
        
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y) 

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    from collections import defaultdict
    G = defaultdict(list)
    D = []
    for i in range(N-1):
        a, b = map(int,input().split())
        D.append([a,b])
        G[a].append(b)
        G[b].append(a)
    que = [[1,[1]]]
    visited = {}
    
    while que != []:
        v = que.pop()
        visited[v[0]] = 1
        if v[0] == N:
            path = v[1]
            break
        else:
            for i in G[v[0]]:
                if not i in visited:
                    que.append([i,v[1]+[i]])
    L = len(path)
    if L%2==0:
        d1,d2 = path[L//2-1],path[L//2]
    else:
        d1,d2 = path[L//2],path[L//2+1]
    G2 = UnionFind(N)
    
    for i in D:
        a,b = i
        if not ((a==d1 and b==d2) or (a==d2 and b==d1)):
            G2.union(a,b)
    one = -G2.par[G2.find(1)]
    enu = -G2.par[G2.find(N)]
    
    if one>enu:
        print("Fennec")
    else:
        print("Snuke")
    

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

p = []
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,path):
        global p
        path =  path  + [n]
        if n == N - 1:
            p = path
        for v in e[n]:
            if col[v] == -1:
                col[v] = c + 1
                dfs(v,c+1,path)
                if p:
                    return
    dfs(0,0,[])

    if len(p) % 2 ==0:
        fn = p[len(p)//2-1]
        sn = p[len(p)//2]
    else:
        fn = p[len(p)//2]
        sn = p[len(p)//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)

   # colsn = [ -1 for i in range(N)]
   # colsn[N-1] = 0
   # def dfs3(n,c):

   #     for v in e[n]:
   #         if v == fn:
   #             continue
   #         elif colsn[v] == -1:
   #             colsn[v] = c + 1
   #             dfs3(v,c+1)

   # dfs3(N-1,0)
    fennec = -1
    #snuke = -1
    for i in range(N):
    #    if colsn[i] != -1:
    #        snuke += 1
        if colfn[i] != -1:
            fennec += 1

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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

p = []
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,path):
        global p
        path = path + [n]
        if n == N - 1:
            p = path
        for v in e[n]:
            if col[v] == -1:
                col[v] = c + 1
                dfs(v,c+1,path)
                if p:
                    return
    dfs(0,0,[])

    if len(p) % 2 ==0:
        fn = p[len(p)//2-1]
        sn = p[len(p)//2]
    else:
        fn = p[len(p)//2]
        sn = p[len(p)//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)

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

        for v in e[n]:
            if v == fn:
                continue
            elif colsn[v] == -1:
                colsn[v] = c + 1
                dfs3(v,c+1)

    dfs3(N-1,0)
    fennec = -1
    snuke = -1
    for i in range(N):
        if colsn[i] != -1:
            snuke += 1
        if colfn[i] != -1:
            fennec += 1

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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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 = []
def dfs(n,c,path):
    global p
    path = path + [n]
    if n == N - 1:
        p = path
    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            dfs(v,c+1,path)
dfs(0,0,[])

if len(p) % 2 ==0:
    fn = p[len(p)//2-1]
    sn = p[len(p)//2]
else:
    fn = p[len(p)//2]
    sn = p[len(p)//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)

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

    for v in e[n]:
        if v == fn:
            continue
        elif colsn[v] == -1:
            colsn[v] = c + 1
            dfs3(v,c+1)

dfs3(N-1,0)
fennec = -1
snuke = -1
for i in range(N):
    if colsn[i] != -1:
        snuke += 1
    if colfn[i] != -1:
        fennec += 1

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

Submission status: Time Limit Exceeded

Solution code:
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

d = {}
for i in range(N+1):
    d[i] = []
d[0].append(0)
p = []
def dfs(n,c,path):
    global p
    path = path + [n]
    if n == N - 1:
        p = path
    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            d[c+1].append((n,v))
            dfs(v,c+1,path)
dfs(0,0,[])
#print(col)
#print(p)

if len(p) % 2 ==0:
    fn = p[len(p)//2-1]
    sn = p[len(p)//2]
else:
    fn = p[len(p)//2]
    sn = p[len(p)//2+1]

#print(fn,sn)

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
#print(fennec)

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

    for v in e[n]:
        if v == fn:
            continue
        elif colsn[v] == -1:
            colsn[v] = c + 1
            dfs3(v,c+1)

dfs3(N-1,0)
snuke = -1
#print(colsn)
for i in range(N):
    if colsn[i] != -1:
        snuke += 1
#print(snuke)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def dfs(graph, start, goal):
    stack = deque()
    push, pop = stack.append, stack.pop
    route = [[] for i in range(N+1)]
    push([start, []])
    route[start] = [start]
    while stack:
        a, r = pop()
        for b in graph[a].keys():
            if route[b] == []:
                push([b, r+[b]])
                route[b] = r+[b]
    return route

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
route = dfs(graph, 1, N)
# print(route)
q_len = len(route[N])
q = route[N][q_len // 2]
nex = route[N][q_len // 2]
tmp = [r for r in route if nex in r]
s_get = len(tmp)
# print(s_get, nex, N-s_get)
print('Fennec' if N - s_get > s_get else 'Snuke')

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
import sys
ab=[list(map(int, input().split())) for _ in range (N-1)]
con=[[] for _ in range(N+1)]

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

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

Submission status: Time Limit Exceeded

Solution code:

# -*- coding: utf-8 -*-

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, x, y):
        '''
        xとyが同じグループならFalse
        xとyが違うグループなら、同じグループにする(くっつける)
        '''
        x1 = self.find(x)
        y1 = self.find(y)

        if x1 == y1:
            return False

        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True

    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
# python template for atcoder1


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):
    if turn == 1:
        if len(S) == 0:
            return
        c = S.pop(0)
        for i in adj[c]:
            #print("i->", i)
            #print("i2->", Un.find(i))
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                #print("union Sun", i)
                Un.union(S_or, i)
                S.append(i)
    else:
        if len(F) == 0:
            return
        c = F.pop(0)
        for i in adj[c]:
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                #print("union Fen", i)
                Un.union(F_or, i)
                F.append(i)
    # print(Un.get_table())
    # print(S)
    # print(F)


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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label not in visited:
        visited.append(label)

        for v in d[label]:
            if v not in visited:
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

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

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

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[0] = 0
bfs(0)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[-1] = 0
bfs(n - 1)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

#print(tekazu_Fennec, tekazu_Snuke)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(start, goal):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        if label not in visited:
            visited.append(label)
            #if label == goal:
            #    return

            for v in d[label]:
                #if v not in visited:
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

n = int(input())
d = {i: [] for i in range(n)}

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

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[0] = 0
bfs(0, n - 1)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[-1] = 0
bfs(n - 1, 0)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

#print(tekazu_Fennec, tekazu_Snuke)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label == goal:
        #    visited.append(label)
        #    return tekazu[goal]

        if label not in visited:
            visited.append(label)

            for v in d[label]:
                if v not in visited:
                    tekazu[v] = tekazu[label] + 1
                    queue.appendleft(v)

    return

n = int(input())
d = {i: [] for i in range(n)}

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

tekazu = [0 for _ in range(n)] # nは頂点数
bfs(0)
tekazu_Fennec = tekazu

tekazu = [0 for _ in range(n)] # nは頂点数
bfs(n - 1)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label == goal:
        #    visited.append(label)
        #    return tekazu[goal]

        if label not in visited:
            visited.append(label)

            for v in d[label]:
                if v not in visited:
                    tekazu[v] = tekazu[label] + 1
                    queue.appendleft(v)

    return

n = int(input())
d = {i: [] for i in range(n)}

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

tekazu = [0 for _ in range(n)] # nは頂点数
bfs(0)
tekazu_Fennec = tekazu

tekazu = [0 for _ in range(n)] # nは頂点数
bfs(n - 1)
tekazu_Snuke = tekazu


Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(start, goal):
    queue = deque([start])
    visited = []
    tekazu = [0 for _ in range(n)] # nは頂点数

    while queue:
        label = queue.pop()

        if label == goal:
            visited.append(label)
            return tekazu[goal]

        if label not in visited:
            visited.append(label)

            for v in d[label]:
                if v not in visited:
                    tekazu[v] = tekazu[label] + 1
                    queue.appendleft(v)

    return False

n = int(input())
d = {i: [] for i in range(n)}

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

Fennec = 0
Snuke = 0

for i in range(n):
    if bfs(0, i) <= bfs(n - 1, i):
        Fennec += 1
    else:
        Snuke += 1

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

Submission status: Time Limit Exceeded

Solution code:
    #相手のパスを潰したい
    # こちら側に来てほしくない場合,最短経路を潰すしか無い
    # 最適を簡単に表せない A - B - C - D
    #                EF-|   |-GH...
    # のとき、A→EFとやっていると、Bを取られて死ぬ
    # でもこれをいちいち計算できない
    # 「相手のパスを潰す」、というのは、最短経路がより短いほうが勝つと考える?
    # でも相手にパスが潰されるかどうかはわからない
    # とりあえずやってみる
n = int(input())
INF = 10**6
graph = [[float("inf")]*n for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1][b -1] = 1
    graph[b - 1][a - 1] = 1
    
#ダイクストラで0, n-1からの最短距離を求める
    
    
import heapq
    
class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush
    
        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue
    
            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist
    
    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal
    
        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]
    
        # 経路をreverseして出力
        return list(reversed(path))
d = Dijkstra()
#print(d.dijkstra(graph, start=0))
#print(d.dijkstra(graph, start=n-1))
cnt = 0
for i, j in zip(d.dijkstra(graph, start=0,), d.dijkstra(graph, start=n-1)):
    if i <= j:
        cnt += 1
print("Fennec" if cnt > n//2 else "Snuke")