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:
from bisect import *
from collections import *
import copy
N=int(input())
AB=[map(int,input().split()) for i in range(N-1)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

stack=deque([[1,0,[1]]])
visited=set([1])
while stack:
    a,m,miti=stack.popleft()
    for p in data[a]:
        if p==N:
            miti.append(N)
            break
        if not p in visited:
            visited.add(a)
            tempmiti=copy.copy(miti)
            tempmiti.append(p)
            stack.append([p,m+1,tempmiti])
miti[m//2 + m%2]
visited=set([miti[m//2 + m%2],miti[m//2 + m%2+1]])
stack=deque([miti[m//2 + m%2]])
count=0
while stack:
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            count+=1
            visited.add(a)
            stack.append(p)
if count>(N-2)//2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

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

    def root(x,y):
        go = [False for _ in range(N)]
        go[x],go[y] = True,True
        q = deque([x])
        count = 0
        while q:
            now = q.pop()
            for fol in dist[now]:
                if go[fol]:
                    continue
                else:
                    go[fol] = True
                    q.append(fol)
                    count += 1
        return count
    
    fen = root(0,N-1)
    snu = root(N-1,0)
    dup = (fen+snu)-N+2
    fen -= dup
    snu -= dup
    fa = -(-dup//2)+fen
    sa = dup//2+snu
    
    if fa > sa:
        print("Fennec")
    else:
        print("Snuke")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

n=I()
g,c=GI(n,n-1)

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

def dfs(x,s):
    r=[]
    for i in x:
        v[i]=s
    for i in x:
        for nb in g[i]:
            if v[nb]==-1:
                r.append(nb)
                v[nb]=s
    return r

F=[0]
S=[n-1]
while F or S:
    F=dfs(F,1)
    S=dfs(S,0)

if sum(v)>=n//2:
    ans='Fennec'
else:
    ans='Snuke'
    
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


ans=0

n=I()
g,c=GI(n,n-1)

show(g)
v=[-1]*n
v[n-1]=0

def dfs(x,s):
    r=[]
    for i in x:
        v[i]=s
    for i in x:
        for nb in g[i]:
            if v[nb]==-1:
                r.append(nb)
                v[nb]=s
    return r

F=[0]
S=[n-1]
while F or S:
    F=dfs(F,1)
#    show('F',v,F,S)
    S=dfs(S,0)
#    show('S',v,F,S)

if sum(v)>=n//2:
    ans='Fennec'
else:
    ans='Snuke'
    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

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

colors = [0 for _ in range(N)]
colors[0] = 1
colors[N-1] = 2

buf = [(0, 1), (N-1, 2)]
while buf:
    src, color = buf.pop()
    for dst, w in edges[src]:
        if colors[dst] == 0:
            colors[dst] = color
            buf.append((dst, color))



if colors.count(1) > colors.count(2):
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

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

dists1 = [float('inf') for _ in range(N)]
used = [False for _ in range(N)]
dists1[0] = 0
used[0] = True

buf = [0]
while buf:
    src = buf.pop()
    for dst, w in edges[src]:
        if not used[dst]:
            dists1[dst] = dists1[src] + w
            used[dst] = True
            buf.append(dst)


dists2 = [float('inf') for _ in range(N)]
used = [False for _ in range(N)]
dists2[N-1] = 0
used[N-1] = True

buf = [N-1]
while buf:
    src = buf.pop()
    for dst, w in edges[src]:
        if not used[dst]:
            dists2[dst] = dists2[src] + w
            used[dst] = True
            buf.append(dst)

num1, num2 = 0, 0
for d1, d2 in zip(dists1, dists2):
    if d1 < d2:
        num1 += 1
    elif d1 > d2:
        num2 += 1


if num1 > num2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  dist = [0]*n
  def dfs(v, seen, end):
    seen[v] = True
    if v == end:
      return
    for nv in F[v]:
      if seen[nv]:
        continue
      dist[nv] = dist[v] + 1
      dfs(nv, seen, end)
  dfs(0, seenB, n-1)
  c = dist[n-1] - 1
  dfs(n-1, seenW, 0)
  aplusd = seenB.count(True) - 2
  bplusd = seenW.count(True) - 2
  d = aplusd + bplusd + 2 - n
  a = aplusd - d
  b = bplusd - d
  if c%2 == 0:
    if a > b:
      print("Fennec")
    else:
      print("Snuke")
  else:
    if a >= b:
      print("Fennec")
    else:
      print("Snuke")
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  dist = [0]*n
  def dfs(v, seen, end):
    seen[v] = True
    if v == end:
      return
    for nv in F[v]:
      if seen[nv]:
        continue
      dist[nv] = dist[v] + 1
      dfs(nv, seen, end)
  dfs(0, seenB, n-1)
  c = dist[n-1]
  dfs(n-1, seenW, 0)
  aplusd = seenB.count(True) - 2
  bplusd = seenW.count(True) - 2
  d = aplusd + bplusd + 2 - n
  a = aplusd - d
  b = bplusd - d
  if c%2 == 0:
    if a > b:
      print("Fennec")
    else:
      print("Snuke")
  else:
    if a >= b:
      print("Fennec")
    else:
      print("Snuke")
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  dist = [0]*n
  seenB[n-1] = True
  seenW[0] = True
  def dfs(v, seen):
    seen[v] = True
    for nv in F[v]:
      dist[nv] = dist[v] + 1
      if seen[nv]:
        continue
      dfs(nv, seen)
  dfs(0, seenB)
  c = dist[n-1]
  dfs(n-1, seenW)
  aplusd = seenB.count(True) - 2
  bplusd = seenW.count(True) - 2
  d = aplusd + bplusd + 2 - n
  a = aplusd - d
  b = bplusd - d
  if c%2 == 0:
    if a > b:
      print("Fennec")
    else:
      print("Snuke")
  else:
    if a >= b:
      print("Fennec")
    else:
      print("Snuke")
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  seenB[n-1] = True
  seenW[0] = True
  def dfs(v, seen):
    seen[v] = True
    for nv in F[v]:
      if seen[nv]:
        continue
      dfs(nv, seen)
  dfs(0, seenB)
  dfs(n-1, seenW)
  aplusc = seenB.count(True) - 2
  bplusc = seenW.count(True) - 2
  c = aplusc + bplusc + 2 - n
  a = aplusc - c
  b = bplusc - c
  if c%2 == 0:
    if a > b:
      print("Fennec")
    else:
      print("Snuke")
  else:
    if a >= b:
      print("Fennec")
    else:
      print("Snuke")
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

n = int(input())
F = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  F[a].append(b)
  F[b].append(a)
seenB = [False]*n
seenW = [False]*n
seenB[n-1] = True
seenW[0] = True
def dfs(v, seen):
  seen[v] = True
  rep = 1
  for nv in F[v]:
    if seen[nv]:
      continue
    rep += dfs(nv, seen)
  return rep
aplusc = dfs(0, seenB) - 2
bplusc = dfs(n-1, seenW) - 2
c = aplusc + bplusc + 2 - n
a = aplusc - c
b = bplusc - c
if c%2 == 0:
  if a > b:
    print("Fennec")
  else:
    print("Snuke")
else:
  if a >= b:
    print("Fennec")
  else:
    print("Snuke")

Submission status: Wrong Answer

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

n = int(input())
F = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  F[a].append(b)
  F[b].append(a)
seenB = [False]*n
seenW = [False]*n
seenB[n-1] = True
seenW[0] = True
def dfs(v, seen):
  seen[v] = True
  rep = 1
  for nv in F[v]:
    if seen[nv]:
      continue
    rep += dfs(nv, seen)
  return rep
aplusc = dfs(0, seenB) - 1
bplusc = dfs(n-1, seenW) - 1
c = aplusc + bplusc + 2 - n
a = aplusc - c
b = bplusc - c
if c%2 == 0:
  if a > b:
    print("Fennec")
  else:
    print("Snuke")
else:
  if a >= b:
    print("Fennec")
  else:
    print("Snuke")

Submission status: Wrong Answer

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  seenB[n-1] = True
  seenW[0] = True
  def dfs(v, seen):
    seen[v] = True
    rep = 1
    for nv in F[v]:
      if seen[nv]:
        continue
      rep += dfs(nv, seen)
    return rep
  aplusc = dfs(0, seenB) - 1
  bplusc = dfs(n-1, seenW) - 1
  c = aplusc + bplusc + 2 - n
  a = aplusc - c
  b = bplusc - c
  if c%2 == 0:
    if a > b:
      print("Fennec")
    else:
      print("Snuke")
  else:
    if a >= b:
      print("Fennec")
    else:
      print("Snuke")
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  seenB[n-1] = True
  seenW[0] = True
  def dfs(v, seen):
    seen[v] = True
    for nv in F[v]:
      if seen[nv]:
        continue
      dfs(nv, seen)
  dfs(0, seenB)
  dfs(n-1, seenW)
  print(seenB, seenW)
  aplusc = seenB.count(True) - 2
  bplusc = seenW.count(True) - 2
  print(aplusc, bplusc)
  c = aplusc + bplusc + 2 - n
  a = aplusc - c
  b = bplusc - c
  print(a, b, c)
  if c%2 == 0:
    if a > b:
      print("Fennec")
    else:
      print("Snuke")
  else:
    if a >= b:
      print("Fennec")
    else:
      print("Snuke")
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  seenB[n-1] = True
  seenW[0] = True
  def dfs(v, seen):
    seen[v] = True
    rep = 1
    for nv in F[v]:
      if seen[nv]:
        continue
      rep += dfs(nv, seen)
    return rep
  aplusc = dfs(0, seenB)
  bplusc = dfs(n-1, seenW)
  c = aplusc + bplusc + 2 - n
  a = aplusc - c
  b = bplusc - c
  if c%2 == 0:
    if a > b:
      print("Fennec")
    else:
      print("Snuke")
  else:
    if a >= b:
      print("Fennec")
    else:
      print("Snuke")
      
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
s = [0]
d1 = [-1] * n
d1[0] = 0
while s:
    d = s.pop()
    for node in g[d]:
        if d1[node] == -1:
            s.append(node)
            d1[node] = d1[d] + 1
s = [n - 1]
d2 = [-1] * n
d2[n - 1] = 0
while s:
    d = s.pop()
    for node in g[d]:
        if d2[node] == -1:
            s.append(node)
            d2[node] = d2[d] + 1
f, s = 0, 0
for i in range(n):
    if d1[i] < d2[i]:
        f += 1
    else:
        s += 1
if f > s:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
read = sys.stdin.read

N, *ab = map(int, read().split())
a, b = zip(*zip(*[iter(ab)] * 2))

graph = csr_matrix(([1] * (N - 1), (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False, indices=[1, N])
d1 = distance[0]
dn = distance[1]

Fennec = -1
for i, j in zip(d1, dn):
    if i <= j:
        Fennec += 1

if Fennec > N - Fennec:
    print('Fennec')
else:
    print('Sunuke')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

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

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

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

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

main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)


def dfs_f(now, kyori):
    kyori_f[now] = kyori
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        # 行ったことがない、白く塗られていない
        if not memo_f[next] and next != n - 1:
            memo_f[next] = True
            dfs_f(next, kyori + 1)


def dfs_s(now, kyori):
    kyori_s[now] = kyori
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        # 行ったことがない、黒く塗られていない
        if not memo_s[next] and next != 0:
            memo_s[next] = True
            dfs_s(next, kyori + 1)


n = int(input())
g = [[] * n 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)

# フェネック
memo_f = [False for i in range(n)]  # 訪れたことがあるか
kyori_f = [float("inf") for i in range(n)]  # 始点からの距離
memo_f[0] = True
dfs_f(0, 0)

# すぬけ
memo_s = [False for i in range(n)]  # 訪れたことがあるか
kyori_s = [float("inf") for i in range(n)]  # 始点からの距離
memo_s[n - 1] = True
dfs_s(n - 1, 0)

black = 0
white = 0
for i in range(n):
    if kyori_f[i] < kyori_s[i]:
        black += 1
    else:
        white += 1

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

Submission status: Wrong Answer

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

F=[0]*N
S=[0]*N

stack=[]
# 番号、距離、親
stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]
# 番号、距離、親
stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

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

Submission status: Wrong Answer

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

stack=[]

import copy

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

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

Submission status: Wrong Answer

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

# 1からNの中間点より手前に、より多くのマスへの分岐を持っていれば勝ち
# 幅優先で、最短ルートを記録する。
from collections import deque
que=deque()

import copy

# [番号, 0からのルート, 親]
que.append([0,[],-1])
Nhalf=None
while que:
  node=que.popleft()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    # Nへの到達ルートの中間点
    route.append(v)
#    print(route)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
#    print(Nhalf,E[Nhalf],"remove:",NhalfNext)
#    print("bef:",E)
    E[Nhalf].remove(NhalfNext)
#    print("after:",E[Nhalf])
#    print(NhalfNext,E[NhalfNext],"remove:",Nhalf)
    E[NhalfNext].remove(Nhalf)
#    print("af:",E)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    que.append([child,newroute,v])

# この木でもう一回数え直す。行ける場所が(N-2)の半数以上であれば勝ち
stack=[]
# 自分、親
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
#  print("reached:",v)
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
#print(count)
if count>=N-count:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

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

# 1からNの中間点より手前に、より多くのマスへの分岐を持っていれば勝ち
# 幅優先で、最短ルートを記録する。
from collections import deque
que=deque()

import copy

# [番号, 0からのルート, 親]
que.append([0,[],-1])
Nhalf=None
while que:
  node=que.popleft()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    # Nへの到達ルートの中間点
    route.append(v)
#    print(route)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
#    print(Nhalf,E[Nhalf],"remove:",NhalfNext)
#    print("bef:",E)
    E[Nhalf]=E[Nhalf].remove(NhalfNext)
#    print("af:",E)
#    print("after:",E[Nhalf])
#    print(NhalfNext,E[NhalfNext],"remove:",Nhalf)
    E[NhalfNext]=E[NhalfNext].remove(Nhalf)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    que.append([child,newroute,v])

# この木でもう一回数え直す。行ける場所が(N-2)の半数以上であれば勝ち
stack=[]
# 自分、親
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
#print(count)
if count>=N-count:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

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

# 1からNの中間点より手前に、より多くのマスへの分岐を持っていれば勝ち
# 幅優先で、最短ルートを記録する。
from collections import deque
que=deque()

import copy

# [番号, 0からのルート, 親]
que.append([0,[],-1])
Nhalf=None
while que:
  node=que.popleft()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    # Nへの到達ルートの中間点
    route.append(v)
#    print(route)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
#    print(Nhalf,E[Nhalf],"remove:",NhalfNext)
#    print("bef:",E)
    E[Nhalf]=E[Nhalf].remove(NhalfNext)
#    print("af:",E)
#    print("after:",E[Nhalf])
#    print(NhalfNext,E[NhalfNext],"remove:",Nhalf)
    E[NhalfNext]=E[NhalfNext].remove(Nhalf)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    que.append([child,newroute,v])

# この木でもう一回数え直す。行ける場所が(N-2)の半数以上であれば勝ち
stack=[]
# 自分、親
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
#print(count)
if count>=N/2:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
res=[0]*n
res[0]=1
res[n-1]=-1
q=[0,n-1]
while q:
    qq=[]
    for i in q:
        v=res[i]
        for j in g[i]:
            if not res[j]:
                res[j]=v
                qq.append(j)
    q=qq
if sum(res)>0:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

from collections import defaultdict
graph = defaultdict(list)
for i in range(n - 1):
    graph[ab[i][0] - 1].append(ab[i][1] - 1)
    graph[ab[i][1] - 1].append(ab[i][0] - 1)

dist_f = [float('inf')] * n
dist_f[0] = 0
stack = [0]
while stack:
    start = stack.pop()
    for target in graph[start]:
        if dist_f[target] == float('inf'):
            dist_f[target] = dist_f[start] + 1
            stack.append(target)

dist_s = [float('inf')] * n
dist_s[n - 1] = 0
stack = [n - 1]
while stack:
    start = stack.pop()
    for target in graph[start]:
        if dist_s[target] == float('inf'):
            dist_s[target] = dist_s[start] + 1
            stack.append(target)

d1 = defaultdict(list)
for i in range(len(dist_f)):
    d1[dist_f[i]].append(i)
d2 = defaultdict(list)
for i in range(len(dist_s)):
    d2[dist_s[i]].append(i)

ts = 0
tmp1 = float('inf')
for key in sorted(list(d2.keys())):
    values = d2[key]
    if key != 0:
        ts += len(values)
    s = 0
    for v in values:
        s += dist_f[v]
    if s <= key * len(values):
        tmp1 = key * len(values)
        break

ts = 0
tmp2 = float('inf')
for key in sorted(list(d1.keys())):
    values = d1[key]
    if key != 0:
        ts += len(values)
    s = 0
    for v in values:
        s += dist_s[v]
    if s < key * len(values):
        tmp2 = key * len(values)
        break


if tmp2 <= tmp1:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

from collections import defaultdict
graph = defaultdict(list)
for i in range(n - 1):
    graph[ab[i][0] - 1].append(ab[i][1] - 1)
    graph[ab[i][1] - 1].append(ab[i][0] - 1)

dist_f = [float('inf')] * n
dist_f[0] = 0
stack = [0]
while stack:
    start = stack.pop()
    for target in graph[start]:
        if dist_f[target] == float('inf'):
            dist_f[target] = dist_f[start] + 1
            stack.append(target)

dist_s = [float('inf')] * n
dist_s[n - 1] = 0
stack = [n - 1]
while stack:
    start = stack.pop()
    for target in graph[start]:
        if dist_s[target] == float('inf'):
            dist_s[target] = dist_s[start] + 1
            stack.append(target)

d1 = defaultdict(list)
for i in range(len(dist_f)):
    d1[dist_f[i]].append(i)
d2 = defaultdict(list)
for i in range(len(dist_s)):
    d2[dist_s[i]].append(i)

ts = 0
tmp1 = float('inf')
for key in sorted(list(d2.keys())):
    values = d2[key]
    if key != 0:
        ts += len(values)
    s = 0
    for v in values:
        s += dist_f[v]
    if s <= key:
        tmp1 = key
        break

ts = 0
tmp2 = float('inf')
for key in sorted(list(d1.keys())):
    values = d1[key]
    if key != 0:
        ts += len(values)
    s = 0
    for v in values:
        s += dist_s[v]
    if s < key:
        tmp2 = key
        break


if tmp2 <= tmp1:
    print('Snuke')
else:
    print('Fennec')