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:
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]
    # print(ts, s)
    if s <= ts:
        tmp1 = ts
        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 < ts:
        tmp2 = ts
        break


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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    
q = deque()
q.append(0)
parents = [-1]*N
parents[0] = -2
while q:
    t = q.popleft()
    for i in E[t]:
        if parents[i] == -1:
            parents[i] = t
            q.append(i)
    if parents[N-1] >= 0:
        break

q_snuke = deque()
q_snuke.append(N-1)
idx = N-1
used = [0]*N
used[0] = 1
cnt = 0
while parents[idx] >= 0:
    q_snuke.append(parents[idx])
    idx = parents[idx]
    used[idx] = 1

n = len(q_snuke)
for _ in range(n//2+(n%2)):
    q_snuke.pop()
    

while q_snuke:
    t = q_snuke.popleft()
    for i in E[t]:
        if used[i] == 0:
            used[i] = 1
            q_snuke.append(i)

s = sum(used) - (n//2+(n%2))
if s >= N-s:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# (v, dist)
q = deque()
q.append((1, -1))
seen = set()
while len(q) > 0:
    v, dist = q.popleft()
    if v == N:
        break
    seen.add(v)
    for next_v in nl[v]:
        if next_v not in seen:
            q.append((next_v, dist + 1))
shared = dist

# v, p, cnt
q = deque()
q.append((N, 0, -1))
while len(q) > 0:
    v, p, cnt = q.popleft()
    cnt += 1
    for next_v in nl[v]:
        if next_v not in seen and next_v != p:
            q.append((next_v, v, cnt + 1))
s_back = max(0, cnt)

f_back = N - 2 - shared - s_back

if shared % 2 == 0:
    if f_back <= s_back:
        print('Snuke')
    else:
        print('Fennec')
else:
    if s_back <= f_back:
        print('Fennec')
    else:
        print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# (v, dist)
q = deque()
q.append((1, -1))
seen = set()
while len(q) > 0:
    v, dist = q.popleft()
    if v == N:
        break
    seen.add(v)
    for next_v in nl[v]:
        if next_v not in seen:
            q.append((next_v, dist + 1))

if dist % 2 == 0:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
#木
#お互いの始点を目指すのが最善
#import heapq
#heapじゃない
from collections import deque
n = int(input())
Ad = [[] for _ in range(n)]

for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    Ad[ai].append(bi)
    Ad[bi].append(ai)
#0(元々は1)を根とする

P = [-1 for i in range(n)]
D = [-1 for i in range(n)]
Q = deque()
P[0] = 0
D[0] = 0
Q.append(0)
while Q:
    v = Q.popleft()
    d = D[v]
    for u in Ad[v]:
        if P[u]<0:
            P[u] = v
            Q.append(u)
            D[u] = d+1

up = 0
now = n-1
nxt = P[n-1]
while up<D[n-1]//2:
    now = nxt
    nxt = P[nxt]
    up += 1
r = now
d = D[r]
cnt = 0
Q = deque()
Q.append(r)
V = [False]*n
V[now] = True
while Q:
    v = Q.popleft()
    cnt += 1
    for u in Ad[v]:
        if not V[u] and D[u]>d:
            Q.append(u)
            V[u] = True

if cnt>=(n+1)//2:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
node_data = [[] for i in range(n+1)]
node_stuck = deque([])
Fennec = [0] * (n+1)
Snuke = [0] * (n+1)
for i in range(n-1):
    x, y = list(map(int, input().split()))
    node_data[x].append(y)
    node_data[y].append(x)
node_stuck.append([1,0])
finished = set()

while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Fennec[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count+1])
node_stuck.append([n,0])
finished = set()
while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Snuke[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count + 1]) 
f = 0
s = 0

for i in range(1, n):
    if Fennec[i] <= Snuke[i]:
        f += 1
    else:
        s += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
node_data = [[] for i in range(n+1)]
node_stuck = deque([])
Fennec = [0] * (n+1)
Snuke = [0] * (n+1)
for i in range(n-1):
    x, y = list(map(int, input().split()))
    node_data[x].append(y)
    node_data[y].append(x)
node_stuck.append([1,0])
finished = set()
while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Fennec[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count+1])
node_stuck.append([n,0])
finished = set()
while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Snuke[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count + 1]) 
f = 0
s = 0
for i in range(1, n- 1):
    if Fennec[i] <= Snuke[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(si, ei):
  q = deque()
  q.append([si,0])
  done = set([si])
  ds = [0 for _ in range(N)]
  while len(q) > 0:
    prvi, d = q.pop()
    for i in g[prvi][1]:
      if i in done: continue
      ds[i] = d+1
      q.append([i,d+1])
      done.add(i)
  return ds

N = int(input())
g = {i:[0,[]] for i in range(N)}
g[0][0]=1
g[N-1][0]=-1
for _ in range(N-1):
  a,b = map(int,input().split())
  g[a-1][1].append(b-1)
  g[b-1][1].append(a-1)

dslist = dfs(0,N-1)
delist = dfs(N-1,0)

cntb, cntw = 0, 0
for ds, de in zip(dslist[1:N-1], delist[1:N-1]):
  if ds <= de: cntb += 1
  else: cntw += 1
print('Fennec' if cntb>=cntw else 'Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(si, ei):
  q = deque()
  q.append([si,0])
  done = set([si])
  ds = [0 for _ in range(N)]
  while len(q) > 0:
    prvi, d = q.pop()
    for i in g[prvi][1]:
      if i in done: continue
      ds[i] = d+1
      q.append([i,d+1])
      done.add(i)
  return ds

N = int(input())
g = {i:[0,[]] for i in range(N)}
g[0][0]=1
g[N-1][0]=-1
for _ in range(N-1):
  a,b = map(int,input().split())
  g[a-1][1].append(b-1)
  g[b-1][1].append(a-1)

ds = dfs(0,N-1)
de = dfs(N-1,0)

cntb, cntw = 0, 0
for ds, de in zip(ds, de):
  if ds <= de: cntb += 1
  else: cntw += 1
print('Fennec' if cntb>=cntw else 'Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(si, col):
  q = deque()
  q.append(si)
  done = set([])
  while len(q) > 0:
    prvi = q.pop()
    for i in g[prvi][1]:
      if i in done: continue
      if g[i][0] == 0:
        g[i][0] = col
        return True
      elif g[i][0] == col:
        q.append(i)
        done.add(i)
  return False

N = int(input())
g = {i:[0,[]] for i in range(N)}
g[0][0]=1
g[N-1][0]=-1
for _ in range(N-1):
  a,b = map(int,input().split())
  g[a-1][1].append(b-1)
  g[b-1][1].append(a-1)

col = 1
res = True
while res is True:
  if col == 1:
    res = dfs(0,col)
    if res is False:
      print('Snuke')
      exit()
  else:
    res = dfs(N-1,col)
    if res is False:
      print('Fennec')
      exit()
  col *= -1

Submission status: Wrong Answer

Solution code:
#木
#お互いの始点を目指すのが最善
import heapq
n = int(input())
Ad = [[] for _ in range(n)]

for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    Ad[ai].append(bi)
    Ad[bi].append(ai)
#0(元々は1)を根とする

P = [-1 for i in range(n)]
D = [-1 for i in range(n)]
Q = [0]
P[0] = 0
D[0] = 0
while Q:
    v = heapq.heappop(Q)
    d = D[v]
    for u in Ad[v]:
        if P[u]<0:
            P[u] = v
            Q.append(u)
            D[u] = d+1

up = 0
now = n-1
nxt = P[n-1]
while up<D[n-1]//2:
    now = nxt
    nxt = P[nxt]
    up += 1
r = now
d = D[r]
cnt = 0
Q = [r]
V = [False]*n
V[now] = True
while Q:
    v = heapq.heappop(Q)
    cnt += 1
    for u in Ad[v]:
        if not V[u] and D[u]>d:
            Q.append(u)
            V[u] = True

if cnt>=(n+1)//2:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
import itertools
import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
N = int(input())
E = {i:[] for i in range(N+1)}
for i in range(N-1):
    a,b= inputs()
    E[a].append(b)
    E[b].append(a)
stkf = [[1,-1,0]]
visitedf=[0]*(N+1)
visiteds=[0]*(N+1)
stks = [[N,-1,0]]
cntf=0
cnts=0
while stkf:
    v,p,cost=stkf.pop()
    if v==N:
        visitedf[N]=cost
        continue
    visitedf[v]=cost
    cntf+=1
    for i in E[v]:
        if i!=p:
            stkf.append([i,v,cost+1])
while stks:
    v,p,cost=stks.pop()
    if v==1:
        visiteds[1]=cost
        continue
    visiteds[v]=cost
    cnts+=1
    for i in E[v]:
        if i!=p:
            stks.append([i,v,cost+1])
#print(cntf-1,cnts-1,visitedf[N]-1,visiteds[1]-1)
if (visitedf[N]-1)%2!=0:
  cntf=cntf-1-(visitedf[N]-1)//2
  cnts=cnts-1-(visitedf[N]-1)//2-1
else:
  cntf=cntf-1-(visitedf[N]-1)//2
  cnts=cnts-1-(visitedf[N]-1)//2
print("Fennec" if cntf>cnts else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=deque()
    Q.appendleft((0,point))
    
    while Q:
        c,p=Q.pop()
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                Q.appendleft((c+1,np))
    return cost

n=int(input())
d=[[]]*(n+1)
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

if F<=S:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append([b,1])
    else:
        d[a]=[[b,1]]
    if b in d.keys():
        d[b].append([a,1])
    else:
        d[b]=[[a,1]]
        
x=DIJKSTRA(1,d)[1:]
y=DIJKSTRA(n,d)[1:]
#print(x,y)
F=0
S=0
for s,t in zip(x,y):
    if s<t:
        F+=1
    else:
        S+=1
if F<S:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append([b,1])
    else:
        d[a]=[[b,1]]
    if b in d.keys():
        d[b].append([a,1])
    else:
        d[b]=[[a,1]]
        
x=DIJKSTRA(1,d)[1:]
y=DIJKSTRA(n,d)[1:]
#print(x,y)
F=0
S=0
for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1
if F<S:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict 
d=defaultdict(list)
n=int(input())
for i in range(1,n):
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    d[a].append(b)
    d[b].append(a)
q=[0]
dist=[-1]*n 
dist[0]=0 
vis=[0]*n 
vis[0]=1 
while q:
    t=q.pop(0)
    for i in d[t]:
        if not vis[i]:
            vis[i]=1 
            q.append(i)
            dist[i]=dist[t]+1 
di=dist[n-1]
if di&1:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

da = [0]*N
db = [0]*N

qa = deque([0])
visited = [False]*N
visited[0] = True
while qa :
    u = qa.popleft()
    for v in L[u] :
        if not visited[v] :
            visited[v] = True
            da[v] = da[u] + 1
            qa.append(v)

qb = deque([N-1])
visited = [False]*N
visited[N-1] = True
while qb :
    u = qb.popleft()
    for v in L[u] :
        if not visited[v] :
            visited[v] = True
            db[v] = db[u] + 1
            qb.append(v)

c = sum([1 if da[i] < db[i] else 0 for i in range(N)])
ans = "Fennec" if c >= N-c else "Snuke"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

da = [0]*N
db = [0]*N

qa = deque([0])
visited = [False]*N
visited[0] = True
while qa :
    u = qa.popleft()
    for v in L[u] :
        if not visited[v] :
            visited[v] = True
            da[v] = da[u] + 1
            qa.append(v)

qb = deque([N-1])
visited = [False]*N
visited[N-1] = True
while qb :
    u = qb.popleft()
    for v in L[u] :
        if not visited[v] :
            visited[v] = True
            db[v] = db[u] + 1
            qb.append(v)

c = sum([1 if da[i] <= db[i] else 0 for i in range(N)])
ans = "Fennec" if c >= N-c else "Snuke"
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

neighbor = [[] for _ in range(N)]

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

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 点iを与えると、点iからの最短距離のリストを返す
def shortest_distance(home_point):
    shortest_distance_list = [-1]*N
    shortest_distance_list[home_point] = 0
    visited = [0]*N
    visited[home_point] = 1
    next_points = deque([home_point])

    while len(next_points) > 0:
        p = next_points.popleft()
        visited[p] = 1
        for idx in neighbor[p]:
            if visited[idx] == 0:
                shortest_distance_list[idx] = shortest_distance_list[p]+1
                if idx not in next_points:
                    next_points.append(idx)

    return shortest_distance_list

shortest_distance_from_Fennec = shortest_distance(0)
# shortest_distance_from_Snuke = shortest_distance(N-1)

# for idx in range(1,N-1):
#     if shortest_distance_from_Fennec[idx] <= shortest_distance_from_Snuke[idx]:
#         black_white[idx] = 0
#     else:
#         black_white[idx] = 1

# print("Fennec" if black_white.count(0) > black_white.count(1) else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

neighbor = [[0]*N for _ in range(N)]

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

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 点iを与えると、点iからの最短距離のリストを返す
def shortest_distance(home_point):
    shortest_distance_list = [-1]*N
    shortest_distance_list[home_point] = 0
    visited = [0]*N
    next_points = deque([home_point])

    while len(next_points) > 0:
        p = next_points.popleft()
        visited[p] = 1
        for idx in range(N):
            if neighbor[p][idx] > 0 and visited[idx] == 0:
                next_points.append(idx)
                shortest_distance_list[idx] = shortest_distance_list[p]+1

    return shortest_distance_list

shortest_distance_from_Fennec = shortest_distance(0)
# shortest_distance_from_Snuke = shortest_distance(N-1)

# for idx in range(1,N-1):
#     if shortest_distance_from_Fennec[idx] <= shortest_distance_from_Snuke[idx]:
#         black_white[idx] = 0
#     else:
#         black_white[idx] = 1

# print("Fennec" if black_white.count(0) > black_white.count(1) else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

neighbor = [[0]*N for _ in range(N)]
edge = []

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

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 点iを与えると、点iからの最短距離のリストを返す
def shortest_distance(home_point):
    shortest_distance_list = [-1]*N
    shortest_distance_list[home_point] = 0
    visited = [0]*N
    next_points = deque([home_point])
    distance = 1

    while len(next_points) > 0:
        p = next_points.popleft()
        visited[p] = 1
        extend_points = [idx for idx in range(len(neighbor[p])) if neighbor[p][idx] > 0 and visited[idx] == 0]
        for q in extend_points:
            shortest_distance_list[q] = distance
        next_points.extend(extend_points)
        distance += 1

    return shortest_distance_list

shortest_distance_from_Fennec = shortest_distance(0)
shortest_distance_from_Snuke = shortest_distance(N-1)

for idx in range(1,N-1):
    if shortest_distance_from_Fennec[idx] <= shortest_distance_from_Snuke[idx]:
        black_white[idx] = 0
    else:
        black_white[idx] = 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())

neighbor = [[0]*N for _ in range(N)]
edge = []

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

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 各点の辺の本数
n_edge = []
for idx in range(N-1):
    n_edge.append(sum(neighbor[idx]))

# プレイヤーフラグを与えると、そのプレイヤーが塗れる点のリストを返す\
def next_point(player_flag):
    output = []
    player_area = [idx for idx in range(len(black_white)) if black_white[idx] == player_flag]
    for i in player_area:
        for j in neighbor[i]:
            if neighbor[i][j] > 0:
                output.append(j)
    output = [x for x in output if black_white[x] == -1]
    return output

# 点のリストを与えると、その中で最も辺の多い点のうち1つを返す
def max_edge_point(point_list):
    n_max_edge = -1
    for point in point_list:
        n_max_edge = max(n_max_edge, n_edge[point])
    return n_edge.index(n_max_edge)

# 相手の色の点と隣接した点であり、多くの辺を有する点を優先して塗る
# 相手の色の点と隣接した点が1つもないときは、多くの辺を有する点を優先して塗る
player_flag = 0

while black_white.count(-1) > 0:
    turn_player_next_point = next_point(player_flag)
    not_turn_player_next_point = next_point(1^player_flag)
    both_player_next_point = set(turn_player_next_point) & set(not_turn_player_next_point)

    if len(turn_player_next_point) > 0:
        if len(both_player_next_point) > 0:
            black_white[max_edge_point(both_player_next_point)] = player_flag
        else:
            black_white[max_edge_point(next_point(player_flag))] = player_flag
        player_flag = 1^player_flag
    else:
        break

print("Snuke" if player_flag == 0 else "Fennec")

Submission status: Wrong Answer

Solution code:
N = int(input())

neighbor = [[0]*N for _ in range(N)]
edge = []

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

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 各点の辺の本数
n_edge = []
for idx in range(N-1):
    n_edge.append(sum(neighbor[idx]))

# プレイヤーフラグを与えると、そのプレイヤーが塗れる点のリストを返す\
def next_point(player_flag):
    output = []
    player_area = [idx for idx in range(len(black_white)) if black_white[idx] == player_flag]
    for i in player_area:
        for j in neighbor[i]:
            if neighbor[i][j] > 0:
                output.append(j)
    output = [x for x in output if black_white[x] == -1]
    return output

# 点のリストを与えると、その中で最も辺の多い点のうち1つを返す
def max_edge_point(point_list):
    n_max_edge = -1
    for point in point_list:
        n_max_edge = max(n_max_edge, n_edge[point])
    return n_edge.index(n_max_edge)

# 相手の色の点と隣接した点であり、多くの辺を有する点を優先して塗る
# 相手の色の点と隣接した点が1つもないときは、多くの辺を有する点を優先して塗る
player_flag = 0

while black_white.count(-1) > 0:
    if len(next_point(player_flag)) > 0:
        black_white[max_edge_point(next_point(player_flag))] = player_flag
        player_flag = 1^player_flag
    else:
        break

print("Snuke" if player_flag == 0 else "Fennec")

Submission status: Wrong Answer

Solution code:
N=int(input())
E=[[] for i in range(N)]

for i in range(N-1):
    x,y=map(int,input().split())
    x-=1
    y-=1
    E[x].append(y)
    E[y].append(x)


from collections import deque
BACK=[-1]*N

Q=deque([0])

while Q:
    x=Q.pop()

    for to in E[x]:
        if BACK[to]==-1:
            BACK[to]=x
            Q.append(to)

ROAD=[N-1]

while ROAD[-1]!=0:
    ROAD.append(BACK[ROAD[-1]])

LEN=len(ROAD)

COLOR=[-1]*N
QW=deque()
QB=deque()

for i in range(LEN//2):
    COLOR[ROAD[i]]=1
    QB.append(ROAD[i])

for i in range(LEN//2,LEN):
    COLOR[ROAD[i]]=0
    QW.append(ROAD[i])

SW=0
if LEN%2==1:
    SW+=1
SB=0

while QW:
    x=QW.pop()

    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=0
            SW+=1
            QW.append(to)

while QB:
    x=QB.pop()

    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=1
            SB+=1
            QB.append(to)

if SW>=SB:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000000)
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
que = deque([0])
parent = [-1]*N
parent[0] = 0
while que:
    cur = que.pop()
    for nxt in edges[cur]:
        if parent[nxt] < 0:
            parent[nxt] = cur
            que.append(nxt)
cur = N-1
route = [N-1]
while cur:
    cur = parent[cur]
    route.append(cur)
i = len(route)//2
a, b = route[i-1:i+1]
edges[a].remove(b)
edges[b].remove(a)
que = deque([0])
flag = [True]*N
score = 0
while que:
    v0 = que.pop()
    score+=1
    for v in edges[v0]:
        if flag[v]:
            que.append(v)
            flag[v] = False
if score>N//2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000000)
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
def dfs(route):
    v0 = route[-1]
    if v0 == 0:
        for v in edges[0]:
            if v == N-1:
                return route+[N-1]
            res = dfs(route+[v])
            if res:
                return res
    if len(edges[v0]) == 1:
        return False
    for v in edges[v0]:
        if v == N-1:
            return route+[N-1]
        if v != route[-2]:
            res = dfs(route+[v])
            if res:
                return res
    return False
route = dfs([0])
i = (len(route)+1)//2 
a, b = route[i-1:i+1]
edges[a].remove(b)
edges[b].remove(a)
que = deque([0])
flag = [True]*N
score = 0
while que:
    v0 = que.pop()
    score+=1
    for v in edges[v0]:
        if flag[v]:
            que.append(v)
            flag[v] = False
if score>N//2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

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

N = int(input())
E = [set() for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  E[a-1].add(b-1)
  E[b-1].add(a-1)

V = [-1 for _ in range(N)]
def dfs(u,count):
  V[u] = count
  for v in E[u]:
    if V[v] == -1:
      dfs(v,count+1)
dfs(0,0)
pathcount = V[N-1]-1
#print(pathcount)

for u in list(E[N-1]):
  if V[u] == V[N-1]-1:
    E[u].remove(N-1)
    E[N-1].remove(u)
#print(E)

def dfs2(u):
  visited[u] = True
  res = 1
  for v in E[u]:
    if not visited[v]:
      res += dfs2(v)
  return res
visited = [False for _ in range(N)]
fennec = dfs2(0) - pathcount
snuke = dfs2(N-1)
#print(fennec,snuke)
if (pathcount % 2 == 0 and fennec > snuke) or (pathcount % 2 == 1 and fennec + 1 > snuke):
  print('Fennec')
else:
  print('Snuke')

Submission status: Wrong Answer

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

N = int(input())
E = [set() for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  E[a-1].add(b-1)
  E[b-1].add(a-1)

V = [-1 for _ in range(N)]
def dfs(u,count):
  V[u] = count
  for v in E[u]:
    if V[v] == -1:
      dfs(v,count+1)
dfs(0,0)
pathcount = V[N-1]-1

for u in list(E[N-1]):
  if V[u] == V[N-1]-1:
    E[u].remove(N-1)
    E[N-1].remove(u)

def dfs2(u):
  visited[u] = True
  res = 1
  for v in E[u]:
    if not visited[v]:
      res += dfs2(v)
  return res
visited = [False for _ in range(N)]
fennec = dfs2(0) - pathcount
snuke = dfs2(N-1)
#print(fennec,snuke)
if (pathcount % 2 == 0 and fennec > snuke) or (pathcount % 2 == 1 and fennec - 1 > snuke):
  print('Fennec')
else:
  print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())

G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append(b)
    G[b].append(a)


def dfs(v, p, c, distance):  # 現在の頂点v, vの親p, 現在の距離c
    distance[v] = c
    for nv in G[v]:
        if visited[nv] is False:
            if nv == p:
                continue
            dfs(nv, v, c+1, distance)
    return


distance_f = [-1]*(N+1)
visited = [False] * (N+1)
dfs(1, -1, 0, distance_f)

distance_s = [-1]*(N+1)
visited = [False] * (N+1)
dfs(N, -1, 0, distance_s)

# print(distance_f)
# print(distance_s)

c = 0
for i in range(1, N+1):
    if distance_f[i] < distance_s[i]:
        c += 1
    elif distance_f[i] > distance_s[i]:
        c -= 1

if c > 0:
    print('Fennec')
elif c < 0:
    print('Snuke')
else:
    if distance_f[N] % 2 == 0:
        print('Fennec')
    else:
        print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())

G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append(b)
    G[b].append(a)


def dfs(v, p, c, distance):  # 現在の頂点v, vの親p, 現在の距離c
    distance[v] = c
    for nv in G[v]:
        if visited[nv] is False:
            if nv == p:
                continue
            dfs(nv, v, c+1, distance)
    return


distance_f = [-1]*(N+1)
visited = [False] * (N+1)
dfs(1, -1, 0, distance_f)

distance_s = [-1]*(N+1)
visited = [False] * (N+1)
dfs(N, -1, 0, distance_s)

# print(distance_f)
# print(distance_s)

c = 0
for i in range(1, N+1):
    if distance_f[i] < distance_s[i]:
        c += 1
    elif distance_f[i] > distance_s[i]:
        c -= 1

if c > 0:
    print('Fennec')
elif c < 0:
    print('Snuke')
else:
    if distance_f[N] % 2 == 0:
        print('Snuke')
    else:
        print('Fennec')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())

G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append(b)
    G[b].append(a)


def dfs(v, p, c, distance):  # 現在の頂点v, vの親p, 現在の距離c
    distance[v] = c
    for nv in G[v]:
        if visited[nv] is False:
            if nv == p:
                continue
            dfs(nv, v, c+1, distance)
    return


distance_f = [-1]*(N+1)
visited = [False] * (N+1)
dfs(1, -1, 0, distance_f)

distance_s = [-1]*(N+1)
visited = [False] * (N+1)
dfs(N, -1, 0, distance_s)

# print(distance_f)
# print(distance_s)

c = 0
for i in range(1, N):
    if distance_f[i] < distance_s[i]:
        c += 1
    elif distance_f[i] > distance_s[i]:
        c -= 1

if c > 0:
    print('Fennec')
elif c < 0:
    print('Snuke')
else:
    if distance_f[N] % 2 == 0:
        print('Snuke')
    else:
        print('Fennec')