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())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
dfs_stack_Fennec=[0]
dfs_stack_Snuke=[N-1]
depth_Fennec=[-1]*N
depth_Snuke=[-1]*N
depth_Fennec[0]=0
depth_Snuke[N-1]=0
while dfs_stack_Fennec or dfs_stack_Snuke:
  s1=dfs_stack_Fennec.pop()
  s2=dfs_stack_Snuke.pop()
  for t1 in graph[s1]:
    if depth_Fennec[t1]==-1:
      depth_Fennec[t1]=depth_Fennec[s1]+1
      dfs_stack_Fennec.append(t1)
  for t2 in graph[s2]:
    if depth_Snuke[t2]==-1:
      depth_Snuke[t2]=depth_Snuke[s2]+1
      dfs_stack_Snuke.append(t2)
for i in range(N):
  if depth_Fennec[i]<=depth_Snuke[i]:
    a+=1
if 2*a>N:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
root=[[0]]
depth=[-1]*N
depth[0]=0
while root:
  R=root.pop()
  s=R[-1]
  if s==N-1:
    one_to_N=R
    break
  for t in graph[s]:
    if depth[t]==-1:
      depth[t]=depth[s]+1
      root.append(R+[t])
d=len(one_to_N)
if d%2==1:
  a,b=one_to_N[d//2],one_to_N[d//2+1]
else:
  a,b=one_to_N[d//2-1],one_to_N[d//2]
graph[a].remove(b)
graph[b].remove(a)

dfs_stackF=[0]
depth1=[-1]*N
depth1[0]=0
dfs_stackS=[N-1]
depth2=[-1]*N
depth2[N-1]=0
while dfs_stackF!=[] or dfs_stackS!=[]:
  if dfs_stackF!=[]:
    s1=dfs_stackF.pop()
  if dfs_stackS!=[]:
    s2=dfs_stackS.pop()
  for t1 in graph[s1]:
    if depth1[t1]==-1:
      depth1[t1]=depth[s1]+1
      dfs_stackF.append(t1)
  for t2 in graph[s2]:
    if depth2[t2]==-1:
      depth2[t2]=depth2[s2]+1
      dfs_stackS.append(t2)
F=max(depth1)
S=max(depth2)
if F>S:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
root=[[0]]
depth=[-1]*N
depth[0]=0
while root:
  R=root.pop()
  s=R[-1]
  if s==N-1:
    one_to_N=R
    break
  for t in graph[s]:
    if depth[t]==-1:
      depth[t]=depth[s]+1
      root.append(R+[t])
d=len(one_to_N)
if d%2==1:
  a,b=one_to_N[d//2],one_to_N[d//2+1]
else:
  a,b=one_to_N[d//2-1],one_to_N[d//2]
graph1=graph[:]
graph2=graph[:]
graph1[a].remove(b)
graph2[b].remove(a)

dfs_stackF=[0]
depth1=[-1]*N
depth1[0]=0
dfs_stackS=[N-1]
depth2=[-1]*N
depth[N-1]=0
while len(dfs_stackF)>0 or len(dfs_stackS)>0:
  if len(dfs_stackF)>0:
    s1=dfs_stackF.pop()
  if len(dfs_stackS)>0:
    s2=dfs_stackS.pop()
  for t1 in graph1[s1]:
    if depth1[t1]==-1:
      depth1[t1]=depth[s1]+1
      dfs_stackF.append(t1)
  for t2 in graph2[s2]:
    if depth2[t2]==-1:
      depth2[t2]=depth[s2]+1
      dfs_stackS.append(t2)
F=max(depth1)
S=max(depth2)
if F>S:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
root=[[0]]
depth=[-1]*N
depth[0]=0
while root:
  R=root.pop()
  s=R[-1]
  if s==N-1:
    one_to_N=R
    break
  for t in graph[s]:
    if depth[t]==-1:
      depth[t]=depth[s]+1
      root.append(R+[t])
d=len(one_to_N)
if d%2==1:
  a,b=one_to_N[d//2],one_to_N[d//2+1]
else:
  a,b=one_to_N[d//2-1],one_to_N[d//2]
graph1=graph[:]
graph2=graph[:]
graph1[a].remove(b)
graph2[b].remove(a)

dfs_stackF=[0]
depth1=[-1]*N
depth1[0]=0
dfs_stackS=[N-1]
depth2=[-1]*N
depth[N-1]=0
while len(dfs_stackF)>0 or len(dfs_stackS)>0:
  if len(dfs_stackF)>0:
    s1=dfs_stackF.pop()
  if len(dfs_stackS)>0:
    s2=dfs_stackS.pop()
  for t1 in graph1[s1]:
    if depth1[t1]==-1:
      depth1[t1]=depth[s1]+1
      dfs_stackF.append(t1)
  for t2 in graph2[s2]:
    if depth2[t2]==-1:
      depth2[t2]=depth[s2]+1
      dfs_stackS.append(t2)
F=max(depth1)
S=max(depth2)
if F>S:
  print("Fennec")
else:
  print("Sunuke")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import queue
N = int(input())
edge = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

def bfs(s):
    dist = defaultdict(lambda:float('inf'))
    dist[s] = 0
    que = queue.Queue()
    que.put(s)
    while que.qsize():
        s = que.get()
        for t in edge[s]:
            if dist[t] > dist[s] + 1:
                dist[t] = dist[s] + 1
                que.put(t)
    return dist

fdist = bfs(1)
sdist = bfs(N)
f = 0
for i in range(1,N+1):
    if fdist[i] <= sdist[i]:
        f += 1
s = N-f
if f > s:
    print('Fennec')
else:
    print('Sunuke')

Submission status: Wrong Answer

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

que = deque([0])
INF = float("inf")
d = [INF] * N
d[0] = 0
while que:
    v = que.popleft()
    for w in G[v]:
        if d[w] <= d[v] + 1:
            continue
        else:
            d[w] = d[v] + 1
            que.append(w)

m = max(d) // 2
q = []
for i, k in enumerate(d):
    if k == m:
        q.append(i)

que1 = deque([N - 1])
INF = float("inf")
d1 = [INF] * N
d1[N - 1] = 0
while que1:
    v = que1.popleft()
    for w in G[v]:
        if d1[w] <= d1[v] + 1 or w in q:
            continue
        else:
            d1[w] = d1[v] + 1
            que1.append(w)

s = 0
for i in d1:
    if i != INF:
        s += 1
f = N - s
if f >= s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

que = deque([0])
INF = float("inf")
d = [INF] * N
d[0] = 0
while que:
    v = que.popleft()
    for w in G[v]:
        if d[w] <= d[v] + 1:
            continue
        else:
            d[w] = d[v] + 1
            que.append(w)

m = max(d) // 2
q = []
for i, k in enumerate(d):
    if k == m:
        q.append(i)

que1 = deque([N - 1])
INF = float("inf")
d1 = [INF] * N
d1[N - 1] = 0
while que1:
    v = que1.popleft()
    for w in G[v]:
        if d1[w] <= d1[v] + 1 or w in q:
            continue
        else:
            d1[w] = d1[v] + 1
            que1.append(w)

s = 0
for i in d1:
    if i != INF:
        s += 1
f = N - s
if f > s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

Black, White = 0, 0
Qb, Qw = [a for a in P[0]], [a for a in P[N-1]]
BVisit, WVisit = [False for i in range(N)], [False for i in range(N)]
BVisit[0], WVisit[N-1] = True, True
while Qb:
    temp = Qb.pop(0)
    if temp != N-1:
        Black += 1
        BVisit[temp] = True
        for n in P[temp]:
            if n != N-1 and BVisit[n] == False and n not in Qb:
                Qb.append(n)
while Qw:
    temp = Qw.pop(0)
    if temp != 0:
        White += 1
        WVisit[temp] = True
        for n in P[temp]:
            if n != 0 and WVisit[n] == False and n not in Qw:
                Qw.append(n)

print("Fennec" if Black > White else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

parent = [-1 for i in range(n)]
dist = [-1 for i in range(n)]
flag = [0 for i in range(n)]

def dfs(s):
    flag[s] = 1
    dist[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag[i]:
                continue
            flag[i] = 1
            parent[i] = v[0]
            dist[i] = v[1] + 1
            q.append((i, d + 1))

parent2 = [-1 for i in range(n)]
dist2 = [-1 for i in range(n)]
flag2 = [0 for i in range(n)]

def dfs_f(s):
    count2 = 0
    flag2[s] = 1
    dist2[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag2[i]:
                continue
            count2 += 1
            flag2[i] = 1
            parent2[i] = v
            dist2[i] = v[1] + 1
            q.append((i, v[1] + 1))
    return count2

parent3 = [-1 for i in range(n)]
dist3 = [-1 for i in range(n)]
flag3 = [0 for i in range(n)]

def dfs_s(s):
    count3 = 0
    flag3[s] = 1
    dist3[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag3[i]:
                continue
            count3 += 1
            flag3[i] = 1
            parent3[i] = v[0]
            dist3[i] = v[1] + 1
            q.append((i, v[1] + 1))
    return count3

dfs(0)
D = dist[n-1]

j = n-1
flag2[n-1] = 1
flag3[0] = 1
for i in range(D):
    if (D - i) >= (D+2)//2:
        flag2[j] = 1
        j = parent[j]
    else:
        flag3[j] = 1
        j = parent[j]

df = dfs_f(0)
ds = dfs_s(n-1)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

parent = [-1 for i in range(n)]
dist = [-1 for i in range(n)]
flag = [0 for i in range(n)]

def dfs(s):
    flag[s] = 1
    dist[s] = 0
    q = deque([s])
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag[i]:
                continue
            flag[i] = 1
            parent[i] = v
            dist[i] = d
            q.append(i)

parent2 = [-1 for i in range(n)]
dist2 = [-1 for i in range(n)]
flag2 = [0 for i in range(n)]

def dfs_f(s):
    count2 = 0
    flag2[s] = 1
    dist2[s] = 0
    q = deque([s])
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag2[i]:
                continue
            count2 += 1
            flag2[i] = 1
            parent2[i] = v
            dist2[i] = d
            q.append(i)
    return count2

parent3 = [-1 for i in range(n)]
dist3 = [-1 for i in range(n)]
flag3 = [0 for i in range(n)]

def dfs_s(s):
    count3 = 0
    flag3[s] = 1
    dist3[s] = 0
    q = deque([s])
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag3[i]:
                continue
            count3 += 1
            flag3[i] = 1
            parent3[i] = v
            dist3[i] = d
            q.append(i)
    return count3

dfs(0)
D = dist[n-1]

j = n-1
flag2[n-1] = 1
flag3[0] = 1
for i in range(D):
    if (D - i) >= (D+2)//2:
        flag2[j] = 1
        j = parent[j]
    else:
        flag3[j] = 1
        j = parent[j]

df = dfs_f(0)
ds = dfs_s(n-1)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

parent = [-1 for i in range(n)]
dist = [-1 for i in range(n)]
flag = [0 for i in range(n)]

def dfs(s):
    flag[s] = 1
    dist[s] = 0
    q = deque([s])
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag[i]:
                continue
            flag[i] = 1
            parent[i] = v
            dist[i] = d
            q.append(i)

parent2 = [-1 for i in range(n)]
dist2 = [-1 for i in range(n)]
flag2 = [0 for i in range(n)]

def dfs_f(s):
    count2 = 0
    flag2[s] = 1
    dist2[s] = 0
    q = deque([s])
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag2[i]:
                continue
            count2 += 1
            flag2[i] = 1
            parent2[i] = v
            dist2[i] = d
            q.append(i)
    return count2

parent3 = [-1 for i in range(n)]
dist3 = [-1 for i in range(n)]
flag3 = [0 for i in range(n)]

def dfs_s(s):
    count3 = 0
    flag3[s] = 1
    dist3[s] = 0
    q = deque([s])
    d = 0
    while len(q) > 0:
        d += 1
        v = q.popleft()
        for i in g[v]:
            if flag3[i]:
                continue
            count3 += 1
            flag3[i] = 1
            parent3[i] = v
            dist3[i] = d
            q.append(i)
    return count3

dfs(0)
D = dist[n-1]

j = n-1
for i in range(D):
    if (D - i) >= (D+2)//2:
        j = parent[j]
        flag2[j] = 1
    else:
        j = parent[j]
        flag3[j] = 1

df = dfs_f(0)
ds = dfs_s(n-1)

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 22 16:27:11 2018

@author: maezawa
"""
from collections import deque

n = int(input())
adj = [[] for _ in range(n+1)]
for i in range(n-1):
    ai, bi = list(map(int, input().split()))
    adj[ai].append(bi)
    adj[bi].append(ai)
    
#print(adj)

node = [0]*(n+1)
f = 1
s = n
node[f] = 1
node[s] = -1

stack1 = deque([f])
stack2 = deque([s])
cnt1 = 0
cnt2 = 0

turn = 1

while stack1 or stack2:
    turn += 1
    if stack1:
        f = stack1.pop()
        for m1 in adj[f]:
            if node[m1] != 0:
                continue
            else:
                node[m1] = turn
                stack1.append(m1)

    if stack2:
        s = stack2.pop()
        for m2 in adj[s]:
            if node[m2] != 0:
                continue
            else:
                node[m2] = -turn
                stack2.append(m2)

cnt = 0
for i in node:
    if i>0:
        cnt += 1
    elif i<0:
        cnt -= 1
if cnt > 0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 22 16:27:11 2018

@author: maezawa
"""
from collections import deque

n = int(input())
adj = [[] for _ in range(n+1)]
for i in range(n-1):
    ai, bi = list(map(int, input().split()))
    adj[ai].append(bi)
    adj[bi].append(ai)
    
#print(adj)

node = [0]*(n+1)
f = 1
s = n
node[f] = 1
node[s] = -1

stack1 = deque([f])
stack2 = deque([s])
cnt1 = 0
cnt2 = 0

turn = 0

while stack1 or stack2:
    turn += 1
    if stack1:
        f = stack1.pop()
        for m1 in adj[f]:
            if node[m1] != 0 and abs(node[m1]) < turn:
                continue
            else:
                node[m1] = turn
                stack1.append(m1)
                cnt1 += 1
    if stack2:
        s = stack2.pop()
        for m2 in adj[s]:
            if node[m2] != 0 and abs(node[m1]) <= turn:
                continue
            else:
                node[m2] = -turn
                stack2.append(m2)
                cnt2 += 1

if cnt1 > cnt2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 22 16:27:11 2018

@author: maezawa
"""
from collections import deque

n = int(input())
adj = [[] for _ in range(n+1)]
for i in range(n-1):
    ai, bi = list(map(int, input().split()))
    adj[ai].append(bi)
    adj[bi].append(ai)
    
#print(adj)

node = [0]*(n+1)
f = 1
s = n
node[f] = 1
node[s] = -1

stack1 = deque([f])
stack2 = deque([s])
cnt1 = 0
cnt2 = 0

while stack1 or stack2:
    if stack1:
        f = stack1.pop()
        for m1 in adj[f]:
            if node[m1] != 0:
                continue
            else:
                node[m1] = 1
                stack1.append(m1)
                cnt1 += 1
    if stack2:
        s = stack2.pop()
        for m2 in adj[s]:
            if node[m2] != 0:
                continue
            else:
                node[m2] = -1
                stack2.append(m2)
                cnt2 += 1

if cnt1 > cnt2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappop, heappush

input = sys.stdin.readline

N = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]


g = Graph()
for _ in range(N - 1):
    a, b = map(int, input().split())
    g.add_edge(a - 1, b - 1)
    g.add_edge(b - 1, a - 1)

d1 = Dijkstra(g, 0)
d2 = Dijkstra(g, N - 1)

cnt1, cnt2 = 0, 0
for i in range(1, N - 1):
    x = d1.shortest_distance(i)
    y = d2.shortest_distance(i)
    if x < y:
        cnt1 += 1
    else:
        cnt2 += 1

if cnt1 > cnt2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [input().rstrip().split() for j in range(n-1)]
graph = [[False for i in range(n)] for j in range(n)]#どこが連結されているか
# graph
for i in range(0,n-1):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=True
# graph
d1 = [0]*n#かかった距離
d2 =[0]*n
cnt = 0
def DFS(v,visited,cnt,d):
    all_visited = True #bool
    for i in range(0,n):
        if(visited[i]==False):
            all_visited = False
    if(all_visited):
        return 1
    visited[v]=True
    for i in range(0,n):
        if(graph[v][i]==False):
            continue
        if(visited[i]):
            continue
        cnt += 1
        d[i]=cnt
        DFS(i,visited,cnt,d)
        cnt -= 1


visited=[False]*n
DFS(0,visited,0,d1)
visited=[False]*n

DFS(n-1,visited,0,d2)
# d1
# d2
white=0
black=0
for i in range(1,n-1):
    if d1[i]<=d2[i]:
        black+=1
    else:
        white+=1
if black>=white:
    print('Fennec')
if black<white:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [input().rstrip().split() for j in range(n-1)]
graph = [[False for i in range(n)] for j in range(n)]#どこが連結されているか
# graph
for i in range(0,n-1):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=True
# graph
d1 = [0]*n#かかった距離
d2 =[0]*n
cnt = 0
def DFS(v,visited,cnt,d):
    visited[v]=True
    for i in range(0,n):
        if(graph[v][i]==False):
            continue
        if(visited[i]):
            continue
        cnt += 1
        d[i]=cnt
        DFS(i,visited,cnt,d)
        cnt -= 1


visited=[False]*n
DFS(0,visited,0,d1)
visited=[False]*n

DFS(n-1,visited,0,d2)
# d1
# d2
white=0
black=0
for i in range(0,n):
    if d1[i]<=d2[i]:
        black+=1
    else:
        white+=1
if black>=white:
    print('Fennec')
if black<white:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
l=[[] for _ in [0]*n]
for _ in [0]*(n-1):
  a,b=map(int,input().split())
  l[a-1].extend([(b-1,1)])
  l[b-1].extend([(a-1,1)])
 
dst=[0 for _ in [0]*n]

que=deque([])
v,p,d=0,-1,0
que.append((v,p,d))
while que:
  v,p,d=que.pop()
  dst[v]=d
  for i,j in l[v]:
    if i==p:continue
    que.append((i,v,d+j))

if (dst[n-1]-1)%2:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
INF = 10**6
n = int(input())
path = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [b]
    else:
        path[a].append(b)
    if not b in path.keys():
        path[b] = [a]
    else:
        path[b].append(a)
# print(path)

masu = [None]*(n+1)
masu[1] = 'f'
masu[n] = 's'
stack_f, stack_s = [1], [n]
while True:
    st_f = stack_f[0]
    stack_f = stack_f[1:]
    for en_f in path[st_f]:
        if masu[en_f] not in ['f', 's']:
            masu[en_f] = 'f'
            stack_f.append(en_f)
    if len(stack_f) == 0:
        print('Snuke')
        break

    st_s = stack_s[0]
    stack_s = stack_s[1:]
    for en_s in path[st_s]:
        if masu[en_s] not in ['f', 's']:
            masu[en_s] = 's'
            stack_s.append(en_s)
    if len(stack_s) == 0:
        print('Fennec')
        break
# print(masu)

Submission status: Wrong Answer

Solution code:
INF = 10**6
n = int(input())
path = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    a, b = a-1, b-1
    if not a in path.keys():
        path[a] = [(a, b)]
    else:
        path[a].append((a, b))
    if not b in path.keys():
        path[b] = [(b, a)]
    else:
        path[b].append((b, a))

dist_f = [INF]*n
dist_f[0] = 0
dist_s = [INF]*n
dist_s[-1] = 0
stack_f, stack_s = path[0], path[n-1]
while len(stack_f) > 0 and len(stack_s) > 0:
    st_f, en_f = stack_f[0]
    stack_f = stack_f[1:]
    if dist_f[en_f] < INF:
        pass
    else:
        dist_f[en_f] = dist_f[st_f]+1
        stack_f += path[en_f]

    st_s, en_s = stack_s[0]
    stack_s = stack_s[1:]
    if dist_s[en_s] < INF:
        pass
    else:
        dist_s[en_s] = dist_s[st_s]+1
        stack_s += path[en_s]
# print(dist_f, dist_s)

if n == 2:
    print('Snuke')
else:
    count_f, count_s = 0, 0
    for d_f, d_s in zip(dist_f, dist_s):
        if d_f < d_s:
            count_f += 1
        elif d_s < d_f:
            count_s += 1
    if count_f >= count_s:
        print('Fennec')
    else:
        print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None


def main():
    N = int(input())
    D = [[] for _ in range(N + 1)]

    Fennec, Snuke = [1], [N]

    F_reached, S_reached = [False] * (N + 1), [False] * (N + 1)
    F_reached[1] = True
    S_reached[N] = True

    n_node_between_1_to_n = None

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

    i = 0
    F = [1]
    while len(F) != 0:
        nextF = []
        for f in F:
            for next in D[f]:
                if next == N:
                    n_node_between_1_to_n = i
                    continue

                if not F_reached[next]:
                    nextF.append(next)
                    Fennec.append(next)
                    F_reached[next] = True

        F = nextF[:]
        i += 1

    S = [1]
    while len(S) != 0:
        nextS = []
        for s in S:
            for next in D[s]:
                if next == 1:
                    continue

                if not S_reached[next]:
                    nextS.append(next)
                    Snuke.append(next)
                    S_reached[next] = True

        S = nextS[:]

    if len(Fennec) > len(Snuke):
        print("Fennec")
    elif len(Fennec) < len(Snuke):
        print("Snuke")
    else:
        if n_node_between_1_to_n % 2 == 0:
            print("Snuke")
        else:
            print("Fennec")


main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None

F_MODE = 1
S_MODE = 2

N = None
D = None
Fennec, Snuke = [], []


def dfs(v, prev, mode):
    global Fennec
    global Snuke

    if mode == F_MODE:
        Fennec.append(v)
        endpoint = N
    else:
        Snuke.append(v)
        endpoint = 1

    for next in D[v]:
        if next != prev and next != endpoint:
            dfs(next, v, mode)


def main():
    global D
    global N

    N = int(input())
    D = [[] for _ in range(N + 1)]

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

    dfs(1, -1, F_MODE)
    dfs(N, -1, S_MODE)

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


main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None

F_MODE = 1
S_MODE = 2

N = None
D = None
Fennec, Snuke = [], []


def dfs(v, prev, mode):
    global Fennec
    global Snuke

    if mode == F_MODE:
        Fennec.append(v)
        endpoint = N
    else:
        Snuke.append(v)
        endpoint = 1

    for next in D[v]:
        if next != prev and next != endpoint:
            dfs(next, v, mode)


def main():
    global D
    global N

    N = int(input())
    D = [[] for _ in range(N + 1)]

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

    dfs(1, -1, F_MODE)
    dfs(N, -1, S_MODE)

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


main()