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

#A

#B

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

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
f_bfs_map = [0 for i in range(n)]
q = deque()
q.append(0)
f_bfs_map[0] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != n-1 and not f_bfs_map[y]:
            f_bfs_map[y] = 1
            q.append(y)
s = sum(f_bfs_map)
s_bfs_map = [0 for i in range(n)]
q = deque()
q.append(n-1)
s_bfs_map[n-1] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != 0 and not s_bfs_map[y]:
            s_bfs_map[y] = 1
            q.append(y)
s += sum(s_bfs_map)
s -= n
f_su = sum(f_bfs_map)-s//2+s%2
s_su = sum(s_bfs_map)-s//2
if f_su >= s_su:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

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

#A

#B

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

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
f_bfs_map = [0 for i in range(n)]
q = deque()
q.append(0)
f_bfs_map[0] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != n-1 and not f_bfs_map[y]:
            f_bfs_map[y] = 1
            q.append(y)
s = sum(f_bfs_map)
s_bfs_map = [0 for i in range(n)]
q = deque()
q.append(n-1)
s_bfs_map[n-1] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != 0 and not s_bfs_map[y]:
            s_bfs_map[y] = 1
            q.append(y)
s += sum(s_bfs_map)
s -= n
f_su = sum(f_bfs_map)-s//2+s%2
s_su = sum(s_bfs_map)-s//2
if f_su > s_su:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

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

#A

#B

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

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
bfs_map = [0 for i in range(n)]
q = deque()
q.append(0)
bfs_map[0] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != n-1 and not bfs_map[y]:
            bfs_map[y] = 1
            q.append(y)
s = sum(bfs_map)
bfs_map = [0 for i in range(n)]
q = deque()
q.append(n-1)
bfs_map[n-1] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != 0 and not bfs_map[y]:
            bfs_map[y] = 1
            q.append(y)
s += sum(bfs_map)
s -= n
if s%2:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
N=int(input())
from collections import defaultdict
f=defaultdict(int)
d=defaultdict(list)

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

i=0
b=1
w=1
f[1]=1
f[N]=1
bq=d[1]
wq=d[N]

while len(bq)>0 or len(wq)>0:
    tmp=[]
    if i==0:
        for q in bq:
            if f[q]==0:
                f[q]=1
                b+=1
                tmp+=d[q]
    else:
        for q in wq:
            if f[q]==0:
                f[q]=1
                w+=1
                tmp+=d[q]
    if i==0:
        i=1
        bq=tmp
    else:
        i=0
        wq=tmp

if b>=w:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

n=I()
nl=[[] for i in range(n)]
distfen=[-1 for i in range(n)]
distsnu=[-1 for i in range(n)]

for i in range(n-1):
    a,b=IL()
    nl[a-1].append(b-1)
    nl[b-1].append(a-1)
    
q=[[0,0]]
vis=[False for i in range(n)]
while len(q)!=0:
    s,d=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            distfen[v]=d+1
            q.append([v,d+1])

q=[[0,0]]
vis=[False for i in range(n)]
while len(q)!=0:
    s,d=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            distsnu[v]=d+1
            q.append([v,d+1])
        
fen=0
snu=0

for i in range(1,n-1):
    if distfen[i]<=distsnu[i]:
        fen+=1
    else:
        snu+=1
    
if fen>snu:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

n=I()
nl=[[] for i in range(n)]
distfen=[-1 for i in range(n)]
distsnu=[-1 for i in range(n)]

for i in range(n-1):
    a,b=IL()
    nl[a-1].append(b-1)
    nl[b-1].append(a-1)
    
q=[[0,0]]
vis=[False for i in range(n)]
while len(q)!=0:
    s,d=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            distfen[v]=d+1
            q.append([v,d+1])

q=[[0,0]]
vis=[False for i in range(n)]
while len(q)!=0:
    s,d=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            distsnu[v]=d+1
            q.append([v,d+1])
        
fen=0
snu=0

for i in range(1,n-1):
    if distfen[i]>=distsnu[i]:
        fen+=1
    else:
        snu+=1
    
if fen>snu:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

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

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

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

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

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

snu=len(path)-fen

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

print(5)

Submission status: Wrong Answer

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

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

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

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

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

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

snu=len(path)-fen

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

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra:

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

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

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

            if dist[src] < prev_cost:
                continue

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

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

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

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

        return list(reversed(path))


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

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

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

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

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra:

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

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

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

            if dist[src] < prev_cost:
                continue

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

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

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

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

        return list(reversed(path))

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

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

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

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

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra:

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

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

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

            if dist[src] < prev_cost:
                continue

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

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

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

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

        return list(reversed(path))

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

path = Dijkstra(graph, 0, N-1).execute()
cost = len(path) - 1
path = set(path)
black = 1
if cost % 2 == 0:
    tmp = (cost - 1) // 2
    black += tmp + 1
else:
    tmp = (cost - 1) // 2
    black += tmp

visited = [False for _ in range(N)]
q = [0]
visited[0] = False
while len(q) != 0:
    dist = q.pop()
    for d in graph[dist].keys():
        if visited[d] or d in path:
            continue
        q.append(d)
        visited[d] = True
for v in visited:
    if v:
        black += 1
white = N- black

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

Submission status: Wrong Answer

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, 1))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, 1))

fennec = [float('inf')] * (N+1)
snuke = [float('inf')] * (N+1)
# 木の最短経路を算出するDFS
def dfs(memo: list, cur: int, prev: int, dist: int) -> None:
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(memo, nxt, cur, dist+cost)

dfs(fennec, 1, -1, 0)
dfs(snuke, N, -1, 0)

group = [set() for i in range(3)]
zero_to_n = fennec[N]
for i in range(2, N):
    # ノードがfennecの後ろにある
    if fennec[i] < snuke[i] and snuke[i] > zero_to_n:
        group[0].add(i)
    # ノードがsnukeの後ろにある
    elif fennec[i] > snuke[i] and fennec[i] > zero_to_n:
        group[1].add(i)
    # ノードが2人の間にある
    else:
        group[2].add(i)

# 自分の後方にノードがたくさんある方
if len(group[0]) > len(group[1]):
    print('Fennec')
elif len(group[0]) < len(group[1]):
    print('Snuke')
else:
    # 同率なら2人の間にあるノードの偶奇
    if zero_to_n % 2 == 0:
        print('Snuke')
    else:
        print('Fennec')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
from pprint import pprint as pp
N = int(input())
abn = [list(map(int, input().split())) for _ in range(N-1)]

graph = defaultdict(lambda: defaultdict(int))

for a,b in abn:
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

# pp(graph)

def dist(x):
    que = [(x,0)]
    distance = [-1 for _ in range(N)]
    distance[x] = 0

    while len(que) > 0:
        i,tmpdist = que.pop(0)        

        for next in [k for k,v in  graph[i].items() if v == 1]:
            if distance[next] == -1:
                distance[next] = tmpdist + 1
                que.append((next, tmpdist + 1))

    return distance

distF = dist(0)
# pp(distF)
distS = dist(N-1)
# pp(distS)

Fcnt = 0
Scnt = 0
for f,s in zip(distF,distS):
    if f > s:
        Scnt += 1
    else:
        Fcnt += 1

if Fcnt >= Scnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
def bfs(graph,start,n,check):
    if check == False:
        arrival = [0 for i in range(n+1)]
    else:
        arrival = [0 for i in range(n+1)]
        arrival[check] = -1
    q = [start]
    arrival[start] = 1
    while len(q) != 0:
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i]] == 0:
                q.append(graph[q[0]][i])
                arrival[graph[q[0]][i]] = arrival[q[0]]+1
        q.pop(0)
    return arrival

n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

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


clean = bfs(graph,1,n,False)
fennec = 0
snuke = 0
for i in range(1,n+1):
    if abs(clean[i]-clean[1]) <= abs(clean[i]-clean[n]):
        fennec += 1
    else:
        snuke += 1

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

Submission status: Wrong Answer

Solution code:
def bfs(graph,start,n,check):
    if check == False:
        arrival = [0 for i in range(n+1)]
    else:
        arrival = [0 for i in range(n+1)]
        arrival[check] = -1
    q = [start]
    arrival[start] = 1
    while len(q) != 0:
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i]] == 0:
                q.append(graph[q[0]][i])
                arrival[graph[q[0]][i]] = arrival[q[0]]+1
        q.pop(0)
    return arrival

n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

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


clean = bfs(graph,1,n,False)
middle = clean[n]-clean[1]-1
black = bfs(graph,1,n,n)
fennec = -1
for i in range(1,n):
    if black[i] >= 1:
        fennec += 1
white = bfs(graph,n,n,1)
snuke = -1
for i in range(2,n+1):
    if white[i] >= 1:
        snuke += 1
fennec = fennec - middle
snuke = snuke - middle

if fennec > snuke:
    print("Fennec")
elif fennec == snuke:
    if middle%2 == 0:
        print("Snuke")
    else:
        print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
for i in range(n - 1):#h:高さ
    c.append([int(m) - 1 for m in input().split()])
for i in range(n - 1):
    c[i].append(1)

def DFS(K, w,edges,N):
  cnt = 0
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    cnt += 1
    if label != w:
        for i,c in roots[label]:
          if dist[i]==-1:
            dist[i]=dist[label]+c
            stack+=[i]
  return cnt - 1

def DFS2(K,w,edges,N):
  htg = []
  prl = []
  for i in range(n):
      htg.append([])
      prl.append([])
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  htg[0].append(0)
  while stack:
      label = stack.pop(-1)
      if label != 0:
        htg[label] += htg[prl[label][0]]
        htg[label].append(label)
      for i,c in roots[label]:
        if dist[i]==-1:
          dist[i]=dist[label]+c
          stack+=[i]
          prl[i].append(label)
        if i==w:
          htg[i] += htg[prl[i][0]]
          htg[i].append(i)
          return [dist[w],htg[w]]
root = DFS2(0, n - 1, c, n)[0]#点は0始まり
htgn = DFS2(0, n - 1, c, n)[1]
sroot = (root - 1) // 2
pnt = htgn[sroot + 1]

fenneccnt = DFS(0, pnt, c, n)#点は0始まり
snukecnt = n - fenneccnt
if fenneccnt > snukecnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
for i in range(n - 1):#h:高さ
    c.append([int(m) - 1 for m in input().split()])
for i in range(n - 1):
    c[i].append(1)

def DFS(K,edges,N):
  cnt = 0
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    cnt += 1
    if label != n - 1:
        for i,c in roots[label]:
          if dist[i]==-1:
            dist[i]=dist[label]+c
            stack+=[i]
  return cnt - 1

def DFS2(K,w,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
      if i==w:
        return dist[w]
root = DFS2(0, n - 1, c, n)#点は0始まり
sroot = (root - 1) // 2

fenneccnt = DFS(0, c, n) - sroot#点は0始まり
snukecnt = n - fenneccnt
if fenneccnt > snukecnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
for i in range(n - 1):#h:高さ
    c.append([int(m) - 1 for m in input().split()])
for i in range(n - 1):
    c[i].append(1)

def DFS(K,edges,N):
  cnt = 0
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    cnt += 1
    if label != n - 1:
        for i,c in roots[label]:
          if dist[i]==-1:
            dist[i]=dist[label]+c
            stack+=[i]
  return cnt - 1
fenneccnt = DFS(0, c, n)#点は0始まり
snukecnt = n - fenneccnt
if fenneccnt > snukecnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
g = defaultdict(list)

for i in range(N-1):
    a,b = list(map(int,input().split()))
    g[a] += [b]
    g[b] += [a]
    
g = dict(g)

def bfs(g, st):
    queue = [st]
    INF = 10e+10
    distances = [INF for i in range(N)]
    distances[st-1] = 0
    
    while queue:
        node = queue.pop(0)
        for h in g[node]:
            if distances[h-1] == INF:
                distances[h-1] = distances[node-1] + 1
                queue += g[node]

    return distances

fs = bfs(g, 1)
en = bfs(g, N)
cnt = 0

for i,j in zip(fs,en):
    if(i>=j):
        cnt += 1
    else:
        cnt -= 1

print("Snuke" if cnt > 0 else "Fennec")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
g = defaultdict(list)

for i in range(N-1):
    a,b = list(map(int,input().split()))
    g[a] += [b]
    g[b] += [a]
    
g = dict(g)

def bfs(g, st):
    queue = [st]
    visited = []
    INF = 10e+10
    distances = [0 for i in range(N)]
    
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            for h in set(g[node])-set(visited):
                distances[h-1] = distances[node-1] + 1
            queue += g[node]
    return distances

fs = bfs(g, 1)
en = bfs(g, N)
cnt = 0

for i,j in zip(fs,en):
    if(i>j):
        cnt += 1
    else:
        cnt -= 1

print("Snuke" if cnt > 0 else "Fennec")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**9)

def dps(road,dist,node,d):
    for x in road[node]:
        if dist[x]<0:
            dist[x]=d
            dps(road,dist,x,d+1)
    
N=int(input())
road=[[] for _ in range(N)]
f_d=[-1 for _ in range(N)]
s_d=[-1 for _ in range(N)]
f_d[0]=0
s_d[-1]=0

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

dps(road,f_d,0,1)
dps(road,s_d,N-1,1)

white=0
black=0

for i in range(N-1):
    if f_d[i]<=s_d[i]:
        black+=1
    else:
        white+=1

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

Submission status: Wrong Answer

Solution code:
N=int(input())
road=[[] for _ in range(N)]
used=[0 for _ in range(N)]

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

start=0
for i in range(N):
    if len(road[i])==1:
        start=i
        break
used[start]=1

f=0
s=0
for i in range(N):
    if start == 0:
        f=i
    elif start ==N-1:
        s=i
    for x in road[start]:
        if used[x]!=1:
            start=x

mid=(N-1)/2
if abs(mid-f)<abs(mid-s):
    print('Fennec')
elif abs(mid-f)>abs(mid-s):
    print('Snuke')
else:
    if N%2==0:
        print('Snuke')
    else:
        print('Fennec')