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: Wrong Answer

Solution code:
import itertools
from collections import deque

def distance(edge,v):
    n = len(edge)
    visited = [-1]*n
    dist = [0]*n
    que = deque()
    for i in edge[v]:
        que.append([i,1])
        dist[i]=1
        visited[i]=1
    visited[n-1]=1
    visited[0]=1
    while que:
        vertex_=que.popleft()
        d = vertex_[1]
        vertex = vertex_[0]
        visited[vertex]=1

        for next_v in edge[vertex]:
            if visited[next_v]!=-1:continue
            if(next_v==n-1 or next_v==0):
                continue
            dist[next_v]=dist[vertex]+1
            que.append([next_v,dist[next_v]])
    return dist

def main():
    n=int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    mx_d=0
    fenec = distance(edge,0)
    snuke = distance(edge,n-1)
    dis = snuke[0]
    f=0
    s=0
    dis=1
    for i in range(n-1):
        if(fenec[i]>0 and snuke[i]>0):
            continue
        else:
            if(fenec[i]>0):
                f+=1
            if(snuke[i]>0):
                s+=1
    if(dis%2==0):
        if(f>=s):
            print("Fennec")
        else:
            print("Snuke")
    else:
        if(s>=f):
            print("Snuke")
        else:
            print("Fennec")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque

def distance(edge,v):
    n = len(edge)
    visited = [-1]*n
    dist = [0]*n
    que = deque()
    for i in edge[v]:
        que.append([i,1])
        dist[i]=1
        visited[i]=1
    visited[n-1]=1
    visited[0]=1
    res = 0
    while que:
        vertex_=que.popleft()
        d = vertex_[1]
        vertex = vertex_[0]
        visited[vertex]=1

        for next_v in edge[vertex]:
            if visited[next_v]!=-1:continue
            if(vertex!=abs(v-(n-1))):
                dist[next_v]=dist[vertex]+1
            else:
                dist[next_v]=-10000000
            que.append([next_v,dist[next_v]])
    return dist

def main():
    n=int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    mx_d=0
    fenec= distance(edge,0)
    snuke = distance(edge,n-1)
    f=0
    s=0
    dis = snuke[0]
    snuke[0]=0
    fenec[n-1]=0
    for i in range(n-1):
        if(fenec[i]>0 and snuke[i]>0):
            continue
        else:
            if(fenec[i]>0):
                f+=1
            if(snuke[i]>0):
                s+=1

    if(f>s):
        print("Fennec")
    elif(s>f):
        print("Snuke")
    else:
        if(dis%2==0):
            print("Fennec")
        else:
            print("Snuke")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque

def distance(edge,v):
    n = len(edge)
    visited = [-1]*n
    dist = [0]*n
    que = deque()
    for i in edge[v]:
        que.append([i,1])
        dist[i]=1
        visited[i]=1
    visited[n-1]=1
    visited[0]=1
    res = 0
    while que:
        vertex_=que.popleft()
        d = vertex_[1]
        vertex = vertex_[0]
        visited[vertex]=1

        for next_v in edge[vertex]:
            if visited[next_v]!=-1:continue
            if(vertex!=abs(v-(n-1))):
                dist[next_v]=dist[vertex]+1
            else:
                dist[next_v]=-10000000
            que.append([next_v,dist[next_v]])
    return dist

def main():
    n=int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    mx_d=0
    fenec= distance(edge,0)
    snuke = distance(edge,n-1)
    f=0
    s=0
    for i in range(n-1):
        if(fenec[i]>0 and snuke[i]>0):
            continue
        else:
            if(fenec[i]>0):
                f+=1
            if(snuke[i]>0):
                s+=1

    if(snuke[0]%2==1 and s>=f):
        print("Snuke")
    else:
        print("Fennec")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque

def distance(edge,v):
    n = len(edge)
    visited = [-1]*n
    dist = [0]*n
    que = deque()
    for i in edge[v]:
        que.append([i,1])
        dist[i]=1
        visited[i]=1
    visited[n-1]=1
    visited[0]=1
    while que:
        vertex_=que.popleft()
        d = vertex_[1]
        vertex = vertex_[0]
        visited[vertex]=1

        for next_v in edge[vertex]:
            if visited[next_v]!=-1:continue
            if(next_v==n-1 or next_v==0):
                continue
            dist[next_v]=dist[vertex]+1
            que.append([next_v,dist[next_v]])
    return dist

def main():
    n=int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    mx_d=0
    fenec = distance(edge,0)
    snuke = distance(edge,n-1)
    f=0
    s=0
    dis=1
    for i in range(n-1):
        if(fenec[i]>0 and snuke[i]>0):
            dis = fenec[i]+snuke[i]
        else:
            if(fenec[i]>0):
                f+=1
            if(snuke[i]>0):
                s+=1
    if(dis%2==0):
        if(f>=s):
            print("Fennec")
        else:
            print("Snuke")
    else:
        if(s>=f):
            print("Snuke")
        else:
            print("Fennec")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque

def distance(edge,v):
    n = len(edge)
    visited = [-1]*n
    dist = [0]*n
    que = deque()
    for i in edge[v]:
        que.append([i,1])
        dist[i]=1
        visited[i]=1
    visited[n-1]=1
    visited[0]=1
    while que:
        vertex_=que.popleft()
        d = vertex_[1]
        vertex = vertex_[0]
        visited[vertex]=1

        for next_v in edge[vertex]:
            if visited[next_v]!=-1:continue
            if(next_v==n-1 or next_v==0):
                continue
            dist[next_v]=dist[vertex]+1
            que.append([next_v,dist[next_v]])
    return dist

def main():
    n=int(input())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    mx_d=0
    fenec = distance(edge,0)
    snuke = distance(edge,n-1)

    f=0
    s=0
    dis=1
    for i in range(n-1):
        if(fenec[i]>0 and snuke[i]>0):
            dis = fenec[i]+snuke[i]
        else:
            if(fenec[i]>0):
                f+=1
            else:
                s+=1
    if(dis%2==0):
        if(f>=s):
            print("Fennec")
        else:
            print("Snuke")
    else:
        if(s>=f):
            print("Snuke")
        else:
            print("Fennec")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
print("Fennec")

Submission status: Wrong Answer

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)

fennec = [0]
sunuke = [n-1]
visited = [False]*n
visited[0] = True
fennec_score = 1
visited[n-1] = True
sunuke_score = 1
while True:
    # fennec's turn
    if not fennec:
        pass
    else:
        new_fennec = []
        for f in fennec:
            for to in g[f]:
                if not visited[to]:
                    new_fennec.append(to)
                    visited[to] = True
                    fennec_score+=1
        fennec = new_fennec
    
    # sunuke's turn
    if not sunuke:
        pass
    else:
        new_sunuke = []
        for f in sunuke:
            for to in g[f]:
                if not visited[to]:
                    new_sunuke.append(to)
                    visited[to] = True
                    sunuke_score+=1
        sunuke = new_sunuke
    if not fennec or sunuke:
        break
if fennec_score > sunuke_score:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

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)

fennec = [0]
sunuke = [n-1]
visited = [False]*n
visited[0] = True
visited[n-1] = True
while True:
    # fennec's turn
    if not fennec:
        print('Snuke')
        break
    else:
        new_fennec = []
        for f in fennec:
            for to in g[f]:
                if not visited[to]:
                    new_fennec.append(to)
                    visited[to] = True
        fennec = new_fennec
    
    # sunuke's turn
    if not sunuke:
        print('Fennec')
        break
    else:
        new_sunuke = []
        for f in sunuke:
            for to in g[f]:
                if not visited[to]:
                    new_sunuke.append(to)
                    visited[to] = True
        sunuke = new_sunuke

Submission status: Wrong Answer

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)

fennec = [0]
sunuke = [n-1]
visited = [False]*n
visited[0] = True
visited[n-1] = True
while True:
    # fennec's turn
    if not fennec:
        print('Sunuke')
        break
    else:
        new_fennec = []
        for f in fennec:
            for to in g[f]:
                if not visited[to]:
                    new_fennec.append(to)
                    visited[to] = True
        fennec = new_fennec
    
    # sunuke's turn
    if not sunuke:
        print('Fennec')
        break
    else:
        new_sunuke = []
        for f in sunuke:
            for to in g[f]:
                if not visited[to]:
                    new_sunuke.append(to)
                    visited[to] = True
        sunuke = new_sunuke

Submission status: Wrong Answer

Solution code:
n=int(input())

L=[[] for i in range(n+1)]

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

fe=[0 for i in range(n+1)]
que=[(1,0)]
visited=[0 for i in range(n+1)]
visited[1]=1
head=0

while len(que)>head:
    now=que[head]
    head+=1
    fe[now[0]]=now[1]
    for nex in L[now[0]]:
        if visited[nex]==0:
            visited[nex]=1
            que.append((nex,now[1]+1))
            
sn=[0 for i in range(n+1)]
que=[(n,0)]
visited=[0 for i in range(n+1)]
visited[-1]=1
head=0

while len(que)>head:
    now=que[head]
    head+=1
    sn[now[0]]=now[1]
    for nex in L[now[0]]:
        if visited[nex]==0:
            visited[nex]=1
            que.append((nex,now[1]+1))

kaname=[]
for i in range(1,n+1):
    ck=fe[i]-sn[i]
    if ck==1 or ck==0:
        kaname.append(i)

cnt=0
que=[(1,0)]
visited=[0 for i in range(n+1)]
visited[1]=1
head=0

while len(que)>head:
    now=que[head]
    head+=1
    cnt+=1
    for nex in L[now[0]]:
        if visited[nex]==0 and not now[0] in kaname:
            visited[nex]=1
            que.append((nex,now[1]+1))

if cnt*2>n:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
da = [0]*n
dn = [0]*n
from collections import deque

def bfs(s,d):
  que = deque()
  que.append((s,1))
  chk = [False]*n
  chk[s] = True
  cnt = 1
  while que:
      now,p = que.popleft()
      if cnt == n:
        break
      for i in g[now]:
          if not chk[i]:
            d[i] = p
            chk[i] = True
            cnt += 1
            que.append((i,p+1))
            
bfs(0,da)
bfs(n-1,dn)

f = 0
s = 0
for i in range(n):
  if da[i] <= dn[i]:
    f += 1
  else:
    s += 1
if f > s:
  print('Fennec')
else:
  print('snuke')

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque

    n = int(readline())
    edge = defaultdict(list)

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

    que1 = deque()
    que1.append(0)
    que2 = deque()
    que2.append(n - 1)

    color = [-1] * n

    while que1 or que2:
        if que1:
            u = que1.popleft()
            color[u] = 1
            for v in edge[u]:
                if color[v] == -1:
                    que1.append(v)
                    color[v] = 1
        if que2:
            u = que2.popleft()
            color[u] = 0
            for v in edge[u]:
                if color[v] == -1:
                    que2.append(v)
                    color[v] = 0

    fennec = color.count(1)
    snuke = color.count(0)
    if fennec > snuke:
        print("Fennec")
    else:
        print("Snuke")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque

    n = int(readline())
    edge = defaultdict(list)

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

    que1 = deque()
    que1.append(0)
    que2 = deque()
    que2.append(n - 1)

    color = [-1] * n
    color[n - 1] = 0
    color[0] = 1

    while que1 or que2:
        if que1:
            u = que1.popleft()
            for v in edge[u]:
                if color[v] == -1:
                    que1.append(v)
                    color[v] = 1
        if que2:
            u = que2.popleft()
            for v in edge[u]:
                if color[v] == -1:
                    que2.append(v)
                    color[v] = 0

    if color.count(1) > color.count(0):
        print("Fennec")
    else:
        print("Snuke")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque

    n = int(readline())
    edge = defaultdict(list)

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

    que1 = deque()
    que1.append(0)
    que2 = deque()
    que2.append(n - 1)

    color = [-1] * n
    color[n - 1] = 0
    color[0] = 1

    while que1 or que2:
        u = que1.popleft()
        for v in edge[u]:
            if color[v] == -1:
                que1.append(v)
                color[v] = 1
        if not que1:
            print("Snuke")
            return

        u = que2.popleft()
        for v in edge[u]:
            if color[v] == -1:
                que2.append(v)
                color[v] = 0
        else:
            print("Fennec")
            return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
def bfs(s):
    visited=[-1]*n
    q=deque([s])
    visited[s]=0
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==-1:
                visited[nx]=visited[x]+1
                q.append(nx)
    return visited
visited1=bfs(0)
visitedn=bfs(n-1)
dist=visited1[n-1]-1
if dist%2:
    for i in range(n):
        if visited1[i]==-(-dist//2) and visitedn[i]==-(-dist//2):
            a=i
        if visited1[i]==-(-dist//2)+1 and visitedn[i]==-(-dist//2)-1:
            b=i
else:
    for i in range(n):
        if visited1[i]==-(-dist//2) and visitedn[i]==-(-dist//2)+1:
            a=i
        if visitedn[i]==-(-dist//2) and visited1[i]==-(-dist//2)+1:
            b=i
edge[a].remove(b)
edge[b].remove(a)
visited=[0]*n
q=deque([0])
visited[0]=1
while q:
    x=q.popleft()
    for nx in edge[x]:
        if visited[nx]==0:
            visited[nx]=1
            q.append(nx)
fs=sum(visited)+(-dist//2)-1
ss=n-sum(visited)-dist//2-1
if fs>ss:
    print("Fennec")
elif fs==ss:
    if fs==0:
        print("Fennec")
    else:
        print("Snuke")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
def bfs(s):
    visited=[-1]*n
    q=deque([s])
    visited[s]=0
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==-1:
                visited[nx]=visited[x]+1
                q.append(nx)
    return visited
visited1=bfs(0)
visitedn=bfs(n-1)
dist=visited1[n-1]-1
if dist%2:
    for i in range(n):
        if visited1[i]==-(-dist//2) and visitedn[i]==-(-dist//2):
            a=i
        if visited1[i]==-(-dist//2)+1 and visitedn[i]==-(-dist//2)-1:
            b=i
else:
    for i in range(n):
        if visited1[i]==-(-dist//2) and visitedn[i]==-(-dist//2)+1:
            a=i
        if visitedn[i]==-(-dist//2) and visited1[i]==-(-dist//2)+1:
            b=i
edge[a].remove(b)
edge[b].remove(a)
visited=[0]*n
q=deque([0])
visited[0]=1
while q:
    x=q.popleft()
    for nx in edge[x]:
        if visited[nx]==0:
            visited[nx]=1
            q.append(nx)
fs=sum(visited)+(-dist//2)-1
ss=n-sum(visited)-dist//2-1
if fs>ss:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

ignore = [0] * N
route = []

# nowからNまでのルート
def dfs(now, goal, array):
    global route
    if now == goal:
        route = array
        return

    ignore[now] = 1

    for i in dist[now]:
        if ignore[i] != 1:
            newarray = copy.deepcopy(array)
            newarray.append(i)
            dfs(i, goal, newarray)

    ignore[now] = 0

# ルート探索
dfs(0, N - 1, [0])

# NG以外のところで辿れるところの数
def dfs_ter(sta, ng):
    pos = deque([sta])

    ignore = [0] * N
    for i in ng:
        ignore[i] = 1

    cnt = 0
    while len(pos) > 0:
        u = pos.popleft()
        ignore[u] = 1
        cnt += 1
        for i in dist[u]:
            if ignore[i] != 1:
                pos.append(i)

    return cnt

L = len(route)
fen_ter = route[:(L + 2 - 1) // 2]
snu_ter = route[(L + 2 - 1) // 2:]

fen_ans = 0
snu_ans = 0

if snu_ans >= fen_ans:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  

s = 0

d1 = [INF]*N
d1[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d1[v] != INF: continue
    d1[v] = d1[u] + 1
    q.append(v)
    
s = N-1
d2 = [INF]*N
d2[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d2[v] != INF: continue
    d2[v] = d2[u] + 1
    q.append(v)
    
ans = 0
for i in range(N):
  if d1[i]<=d2[i]:
    ans += 1

if ans >= (N+1)//2:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
def dijkstra(s, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev


def main():
    from itertools import accumulate
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk = dijkstra(n, g)

    vis = [False] * (n + 1)

    def f(now, c):
        if vis[now]:
            return

        vis[now] = True
        c += 1
        for _, nxt in g[now]:
            f(nxt, c)

        return c

    nw = dk[1]

    cnt = []
    vis[1] = True
    vis[n] = True
    while nw != n:
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw, 0)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    *a, = accumulate(cnt)
    l = len(a)
    k = l // 2 - 1 if l % 2 == 0 else l // 2
    fn += a[k] if l > 0 else 0
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq


def dijkstra(s, g):
    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev


def main():
    from itertools import accumulate
    from collections import deque
    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]
    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk = dijkstra(n, g)

    vis = [False] * (n + 1)

    def f(x, c):
        if vis[x]:
            return 0

        vis[x] = True
        c += 1
        for _, nxt in g[x]:
            f(nxt, c)

        return c

    nw = dk[1]
    cnt = []
    while nw != n:
        nx = dk[nw]
        vis[nw] = True
        vis[nx] = True
        c = f(nw, 0)
        vis[nx] = False

        cnt.append(c)
        nw = nx
    else:
        vis[n] = True

    fn = 0
    q = deque([1])
    vis[1] = False
    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    *a, = accumulate(cnt)
    l = len(a)
    k = l // 2 - 1 if l % 2 == 0 else l // 2
    fn += a[k] if l > 0 else 0
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq


def dijkstra(s, g):
    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev


def main():
    from itertools import accumulate
    from collections import deque
    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]
    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk = dijkstra(n, g)

    vis = [False] * (n + 1)

    def f(x, c):
        if vis[x]:
            return 0

        vis[x] = True
        c += 1
        for _, nxt in g[x]:
            f(nxt, c)

        return c

    nw = dk[1]
    cnt = []
    while nw != n:
        nx = dk[nw]
        vis[nw] = True
        vis[nx] = True
        c = f(nw, 0)
        vis[nx] = False

        cnt.append(c)
        nw = nx
    else:
        vis[n] = True

    fn = 0
    q = deque([1])
    vis[1] = False
    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    *a, = accumulate(cnt)
    l = len(a)
    k = l // 2 - 1 if l % 2 == 0 else l // 2
    fn += a[k] if l else 0
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()