Problem:


Score : 400 points

Problem Statement

Fennec and Snuke are playing a board game.

On the board, there are N cells numbered 1 through N, and N-1 roads, each connecting two cells. Cell a_i is adjacent to Cell b_i through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.

Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored.
Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell.
More specifically, each player performs the following action in her/his turn:

Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.

Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.

A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.

Constraints

2 \leq N \leq 10^5

1 \leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

If Fennec wins, print Fennec; if Snuke wins, print Snuke.

Sample Input 1

7
3 6
1 2
3 1
7 4
5 7
1 4

Sample Output 1

Fennec

For example, if Fennec first paints Cell 2 black, she will win regardless of Snuke's moves.

Sample Input 2

4
1 4
4 2
2 3

Sample Output 2

Snuke



Sample input:
7
3 6
1 2
3 1
7 4
5 7
1 4


Sample output:
Fennec

Submission status: Wrong Answer

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

visited = [False]*n
que = deque([(0)])
x = 0
while que:
    idx= que.popleft()
    if idx==n-1:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    x += 1
    for to in g[idx]:
        que.append((to))

visited = [False]*n
que = deque([(n-1)])
y = 0
while que:
    idx= que.popleft()
    if idx==0:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    y += 1
    for to in g[idx]:
        que.append((to))
print('Fennec' if x>=y else 'Snuke')

Submission status: Wrong Answer

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

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

G = [[] for _ in range(N + 1)]
for el in ab:
    a, b = el
    G[a].append(b)
    G[b].append(a)

seen = [False] * (N + 1)
todo = queue.Queue()
dist = [0] * (N + 1)
prev = [None] * (N + 1)

def bfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            todo.put(child)
            dist[child] = dist[parent] + 1
            prev[child] = parent
    if not todo.empty():
        bfs(todo.get())

bfs(1)
#print(dist)
#print(prev)
min_dist = dist[N]
#print(min_dist)

route = []
temp = N
for _ in range(min_dist + 1):
    route.append(temp)
    temp = prev[temp]
#print(route)


seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    cnt[0] += 1
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)


S = route[(min_dist + 1) // 2 - 1]
F = route[(min_dist + 1) // 2]

seen[S] = True
seen[F] = True
cnt = [0]
dfs(S)
arround_S = cnt[0]
cnt = [0]
dfs(F)
arround_F = cnt[0]
#print(arround_N, arround_1)

if arround_F > arround_S:
    print('Fennic')
else:
    print('Snuke')

Submission status: Wrong Answer

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

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

G = [[] for _ in range(N + 1)]
for el in ab:
    a, b = el
    G[a].append(b)
    G[b].append(a)

seen = [False] * (N + 1)
todo = queue.Queue()
dist = [0] * (N + 1)
prev = [None] * (N + 1)

def bfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            todo.put(child)
            dist[child] = dist[parent] + 1
            prev[child] = parent
    if not todo.empty():
        bfs(todo.get())

bfs(1)
#print(dist)
#print(prev)
min_dist = dist[N]
#print(min_dist)

route = []
temp = N
for _ in range(min_dist + 1):
    route.append(temp)
    temp = prev[temp]
#print(route)


seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    cnt[0] += 1
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)

#from N
seen[route[1]] = True
cnt = [0]
dfs(N)
arround_N = cnt[0]
seen = [False] * (N + 1)
seen[route[-2]] = True
cnt = [0]
dfs(1)
arround_1 = cnt[0]
#print(arround_N, arround_1)

if (min_dist - 1) % 2 == 0:
    if arround_1 > arround_N:
        print('Fennec')
    else:
        print('Snuke')
else:
    if arround_1 >= arround_N:
        print('Fennec')
    else:
        print('Snuke')

Submission status: Wrong Answer

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

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

G = [[] for _ in range(N + 1)]
for el in ab:
    a, b = el
    G[a].append(b)
    G[b].append(a)

seen = [False] * (N + 1)
todo = queue.Queue()
dist = [0] * (N + 1)
prev = [None] * (N + 1)

def bfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            todo.put(child)
            dist[child] = dist[parent] + 1
            prev[child] = parent
    if not todo.empty():
        bfs(todo.get())

bfs(1)
#print(dist)
#print(prev)
min_dist = dist[N]
#print(min_dist)

route = []
temp = N
for _ in range(min_dist + 1):
    route.append(temp)
    temp = prev[temp]
#print(route)


seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    cnt[0] += 1
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)

#from N
seen[route[1]] = True
cnt = [0]
dfs(N)
arround_N = cnt[0]
seen[route[-2]] = True
cnt = [0]
dfs(1)
arround_1 = cnt[0]
#print(arround_N, arround_1)

if (min_dist - 1) % 2 == 0:
    if arround_1 > arround_N:
        print('Fennec')
    else:
        print('Snuke')
else:
    if arround_1 >= arround_N:
        print('Fennec')
    else:
        print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


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

    visited = [False]*N
    q1 = deque([0])
    q2 = deque([N-1])
    while q1 and q2:
        v1 = q1.pop()
        while visited[v1]:
            if not q1:
                print("Fennec")
                sys.exit()
            v1 = q1.pop()
        visited[v1] = True

        v2 = q2.pop()
        while visited[v2]:
            if not q2:
                print("Snuke")
                sys.exit()
            v2 = q2.pop()
        visited[v2] = True

        for n1 in edges[v1]:
            if visited[n1]:
                continue
            q1.append(n1)

        for n2 in edges[v2]:
            if visited[n2]:
                continue
            q2.append(n2)
    print("Snuke")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
G = [set() for i in range(N)]

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


F = [-1]*N
F[0] = 0
q = collections.deque()
q.append(0)
while(q):
    x = q.popleft()
    for y in G[x]:
        if F[y] < 0:
            F[y] = F[x] + 1
            q.append(y)

S = [-1]*N
S[N-1] = 0
q.append(N-1)
while(q):
    x = q.popleft()
    for y in G[x]:
        if S[y] < 0:
            S[y] = S[x] + 1
            q.append(y)
# print(F)
# print(S)
ans = 0

q = collections.deque()
q.append(0)
r = [True]*N
r[0] = False
for i in range(N):
    if F[i] + S[i] == F[-1]:
        if F[i] <= S[i]:
            q.append(i)
            r[i] = False
        else:
            r[i] = False
ans = len(q)
while(q):
    x = q.popleft()
    for y in G[x]:
        if r[y]:
            ans += 1
            q.append(y)
            r[y] = False

if ans > N - ans:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
G = [set() for i in range(N)]

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


F = [-1]*N
F[0] = 0
q = collections.deque()
q.append(0)
while(q):
    x = q.popleft()
    for y in G[x]:
        if F[y] < 0:
            F[y] = F[x] + 1
            q.append(y)

S = [-1]*N
S[N-1] = 0
q.append(N-1)
while(q):
    x = q.popleft()
    for y in G[x]:
        if S[y] < 0:
            S[y] = S[x] + 1
            q.append(y)
# print(F)
# print(S)
ans = 0
for i in range(N):
    if F[i] + S[i] == F[-1]:
        ans += 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [[] for _ in range(N)]

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

def calc(s):
    st = [s]
    minDist = [10**18] * N
    minDist[s] = 0
    while st:
        now = st.pop()
        for to in edges[now]:
            if minDist[to] > minDist[now] + 1:
                minDist[to] = minDist[now] + 1
                st.append(to)
    return minDist

A = calc(0)
B = calc(N - 1)

ans = 0
for i in range(N):
    ans += 1 if A[i] <= B[i] else -1
print('Fennec' if ans >= 0 else 'Snuke')

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
G = [set() for i in range(N)]

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


F = [-1]*N
F[0] = 0
q = collections.deque()
q.append(0)
while(q):
    x = q.popleft()
    for y in G[x]:
        if F[y] < 0:
            F[y] = F[x] + 1
            q.append(y)

S = [-1]*N
S[N-1] = 0
q.append(N-1)
while(q):
    x = q.popleft()
    for y in G[x]:
        if S[y] < 0:
            S[y] = S[x] + 1
            q.append(y)
# print(F)
# print(S)
ans = 0
for i in range(N):
    if F[i] <= S[i]:
        ans += 1
if ans >= N // 2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
N = int(input())
from collections import defaultdict
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

dist2 = [-1]*N
que = deque([N-1])
dist[N-1] = 0
while que:
    v = que.popleft()
    d = dist2[v]
    for w in G[v]:
        if dist2[w] > -1:
            continue
        dist2[w] = d + 1
        que.append(w)

ans = [0, 0]
for a,b in zip(dist, dist2):
    if a <= b:
        ans[0] += 1
    else:
        ans[1] += 1


if ans[0] > ans[1]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import heapq
def set_heapq(que, edge, used, v, add_dist=0):
    '''
    確定地点vからつながる辺を全てqueに設定し、返却する

    Parameters
    que : heapque(touple or list)
        辺を管理するキュー (距離、次の行き先)のtopuleまたはlistにて管理
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    v : int
        グラフ上のノード ダイクストラでは確定したノードがvにあたる
    add_dist : int
        確定した地点に足し合わせる距離 スタート地点以外では何かしらの値が追加されることになる

    Returns
    que : heapque(touple or list)
        引数queにvからつながる辺を追加したキュー
    '''
    for a,b in edge[v]:
        if used[b]:
            heapq.heappush(que,(a+add_dist,b))
    return que

def dijkstra_heap(n, s, edge):
    '''
    ダイクストラ法でsで指定された地点からの全てのノードまでの最短距離を返却
    
    Parameters
    n : int
        ノードの数
    s : int
        スタート地点
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている

    Returns
    d : list
        スタート地点から全てのノードの最短距離のリスト
    '''
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s], used[s] = 0, False
    edgelist = set_heapq([], edge, used, s)
    while len(edgelist):
        a, b = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[b]:
            continue
        d[b], used[b] = a, False
        # 確定地点vからつながる辺を全て優先度付きキューに入れる
        edgelist = set_heapq(edgelist, edge, used, b, d[b])
    return d

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

feneec = dijkstra_heap(N, 0, edge)
sunuke = dijkstra_heap(N, N-1, edge)

#print(feneec)
#print(sunuke)

cnt = 0
for i in range(N):
    if feneec[i] >= sunuke[i]:
        cnt += 1

if cnt >= N // 2:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

def dfs(v, parent, dist):
    if dist[v] == -1:
        dist[v] = dist[parent]+1
    for next_v in es[v]:
        if dist[next_v] == -1:
            dfs(next_v,v,dist)

exit()
            
dist0 = [-1] * n
dist0[0] = 0
dfs(0,-1,dist0)


distn = [-1] * n
distn[n-1] = 0
dfs(n-1,-1,distn)

count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    class UnionFind():
        #n個の要素を番号0~n-1で管理する
        #parents:要素の親(1つ上), 要素が根の場合サイズを表す
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        #要素xの根を返す, その過程で経路圧縮も行う
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return
            #それぞれのsizeで比べる
            if self.parents[x] > self.parents[y]:
                x, y = y, x
            self.parents[x] += self.parents[y] #x(根)のsizeを更新
            self.parents[y] = x #yの親を-sizeからxにする

        #xが属するグループのsize
        def size(self, x):
            return -self.parents[self.find(x)]

        #xとyが同じグループかどうか
        def same(self, x, y):
            return self.find(x) == self.find(y)

    uf0 = UnionFind(n=n)
    d = deque([0])
    visited = [0]*n
    while d:
        v = d.popleft()
        visited[v] = 1
        for nv in adj[v]:
            if nv == n-1:
                continue
            if visited[nv] == 0:
                uf0.union(v, nv)
                d.append(nv)

    ufn = UnionFind(n=n)
    d = deque([n-1])
    visited = [0]*n
    while d:
        v = d.popleft()
        visited[v] = 1
        for nv in adj[v]:
            if nv == 0:
                continue
            if visited[nv] == 0:
                ufn.union(v, nv)
                d.append(nv)

    a = uf0.size(0)
    b = ufn.size(n-1)
    common = a + b - n
    if common%2 == 0:
        if a > b:
            print('Fennec')
        else:
            print('Snuke')
    else:
        if a+1 > b:
            print('Fennec')
        else:
            print('Snuke')



if __name__ == '__main__':
    main()

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=a-1
  b=b-1
  G[a].append(b)
  G[b].append(a)
V=[0]*n
V[0]=1
P=[0]*n
P[0]=-1
C=[1]*n
D=deque([0])
DD=deque([0])
GG=[[] for i in range(n)]
while len(D)>0:
  v=D[0]
  D.popleft()
  for i in range(len(G[v])):
    if V[G[v][i]]==0:
      V[G[v][i]]=1
      D.append(G[v][i])
      DD.append(G[v][i])
      P[G[v][i]]=v
DD=list(DD)[::-1]
for i in range(n):
  if DD[i]!=0:
    C[P[DD[i]]]+=C[DD[i]]
a=0
i=n-1
while i!=0:
  i=P[i]
  a=a+1
i=n-1
for i in range((a-1)//2):
  i=P[i]
s=C[i]
f=n-C[i]
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=a-1
  b=b-1
  G[a].append(b)
  G[b].append(a)
V=[0]*n
V[0]=1
P=[0]*n
P[0]=-1
C=[1]*n
D=deque([0])
DD=deque([0])
GG=[[] for i in range(n)]
while len(D)>0:
  v=D[0]
  D.popleft()
  for i in range(len(G[v])):
    if V[G[v][i]]==0:
      V[G[v][i]]=1
      D.append(G[v][i])
      DD.append(G[v][i])
      P[G[v][i]]=v
DD=list(DD)[::-1]
for i in range(n):
  if DD[i]!=0:
    C[P[DD[i]]]+=C[DD[i]]
a=0
i=n-1
while i!=0:
  i=P[i]
  a=a+1
i=n-1
for i in range((a-1)//2):
  i=P[i]
s=C[i]
f=n-C[i]
if s>=f:
  print("Snuke")
else:
  print("Fennec")

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  G[a].append(b)
  G[b].append(a)
V=[0]*n
V[0]=1
P=[0]*n
P[0]=-1
C=[1]*n
D=deque([0])
DD=deque([0])
GG=[[] for i in range(n)]
while len(D)>0:
  v=D[0]
  D.popleft()
  for i in range(len(G[v])):
    if V[G[v][i]]==0:
      V[G[v][i]]=1
      D.append(G[v][i])
      DD.append(G[v][i])
      P[G[v][i]]=v
DD=list(DD)[::-1]
for i in range(n):
  if DD[i]!=0:
    C[P[DD[i]]]+=C[DD[i]]
a=0
i=n-1
while i!=0:
  i=P[i]
  a=a+1
i=n-1
for i in range((a-1)//2):
  i=P[i]
s=C[i]
f=n-C[i]
if s>f:
  print("Sunuke")
else:
  print("Fennec")

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc067/tasks/arc078_b
# 1とNの最短経路について注目したときに、それぞれの最適戦略を考えてみる
# 相手を負かせたい→相手側に攻めて道を塞ぐのが有利(相手のマスが少なくなるから)
# 自分が負けそう→退避して行きたい(でも相手のマスのほうが多かったらもう逆転は不可能)
# 勝者は→先にたどり着けるノードの中で多い方が勝者(同数の場合はFennecが敗者)

import sys
read = sys.stdin.readline
from collections import defaultdict, deque


def read_ints():
    return list(map(int, read().split()))


N = int(input())
graph = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


def ret_dists(u):
    ret = [-1] * N
    que = deque([(u, -1, 0)])  # 現在のノード、前のノード、距離
    ret[u] = 0
    while que:
        u, p, d = que.popleft()
        nd = 1 + d
        for nu in graph[u]:
            if nu == p:  # 親はもう探索しない
                continue
            ret[nu] = nd
            que.append((nu, u, nd))

    return ret


fennec_dist = ret_dists(0)
snuke_dist = ret_dists(N - 1)

n_snuke = 0  # snukeに近いノードの数
n_fennec = 0
for f, s in zip(fennec_dist, snuke_dist):
    if f > s:  # すぬけにちかい
        n_snuke += 1
    elif s > f:
        n_fennec += 1

# print(n_fennec, n_snuke)
if n_fennec == n_snuke:
    if n_fennec + n_snuke != N:
        print('Fennec')
    else:
        print('Snuke')
elif n_fennec > n_snuke:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc067/tasks/arc078_b
# 1とNの最短経路について注目したときに、それぞれの最適戦略を考えてみる
# 相手を負かせたい→相手側に攻めて道を塞ぐのが有利(相手のマスが少なくなるから)
# 自分が負けそう→退避して行きたい(でも相手のマスのほうが多かったらもう逆転は不可能)
# 勝者は→先にたどり着けるノードの中で多い方が勝者(同数の場合はFennecが敗者)

import sys
read = sys.stdin.readline

from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import dijkstra


def read_ints():
    return list(map(int, read().split()))


N = int(input())
graph = lil_matrix((N, N), dtype='int')
# graph = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    graph[a, b] = 1
    graph[b, a] = 1

graph = csr_matrix(graph, dtype='int')
fennec = dijkstra(graph, directed=False, indices=0)
snuke = dijkstra(graph, directed=False, indices=N - 1)

n_snuke_neibor = ((fennec - snuke) > 0).sum()
n_fennec_neibor = ((snuke - fennec) > 0).sum()
# print(n_fennec_neibor, n_snuke_neibor)
if n_fennec_neibor == n_snuke_neibor:
    if n_fennec_neibor + n_snuke_neibor != N:
        print('Fennec')
    else:
        print('Snuke')
elif n_fennec_neibor > n_snuke_neibor:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc067/tasks/arc078_b
# 1とNの最短経路について注目したときに、それぞれの最適戦略を考えてみる
# 相手を負かせたい→相手側に攻めて道を塞ぐのが有利(相手のマスが少なくなるから)
# 自分が負けそう→退避して行きたい(でも相手のマスのほうが多かったらもう逆転は不可能)
# 勝者は→先にたどり着けるノードの中で多い方が勝者(同数の場合はFennecが敗者)

import sys
read = sys.stdin.readline

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


def read_ints():
    return list(map(int, read().split()))


N = int(input())
graph = [[0] * N for _ in range(N)]
# graph = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    graph[a][b] = 1
    graph[b][a] = 1

graph = csr_matrix(graph, dtype='int')
fennec = dijkstra(graph, directed=False, indices=0)
snuke = dijkstra(graph, directed=False, indices=N - 1)

n_snuke_neibor = ((fennec - snuke) > 0).sum()
n_fennec_neibor = ((snuke - fennec) > 0).sum()
# print(n_fennec_neibor, n_snuke_neibor)
if n_fennec_neibor > n_snuke_neibor:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

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

def cur(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        else:
            par[x]=p
            descend[p]+=cur(x)
    neighbor[p].remove(par[p])
    return descend[p]

n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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


x=[descend[n]-1]
t=n
while t!=1:
    t,pret=par[t],t
    x.append(descend[t]-descend[pret]-1)

l=len(x)
p,q=sum(x[:l//2]),sum(x[l//2:])
print("Fennec" if p<q else "Snuke")

Submission status: Wrong Answer

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

def cur(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        else:
            par[x]=p
            descend[p]+=cur(x)
    neighbor[p].remove(par[p])
    return descend[p]

n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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


x=[descend[n]-1]
t=n
while t!=1:
    t,pret=par[t],t
    x.append(descend[t]-descend[pret]-1)

l=len(x)
p,q=sum(x[:l//2]),sum(x[l//2:])
print("Fennec" if p<q else "Sunuke")

Submission status: Wrong Answer

Solution code:
n=int(input())
 
root = [[] for i in range(n)]
for _ in range(n-1):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

stack=[0]
check = [-1]*n
check[0] = 0
count1 = 0
while len(stack):
    v = stack.pop()
    for i in root[v]:
        if i == n-1:
            continue
        if check[i] == -1:
            check[i]=1
            stack.append(i)
            count1 += 1

stack=[n-1]
check = [-1]*n
check[n-1] = 0
count2 = 0
while len(stack):
    v = stack.pop()
    for i in root[v]:
        if i == 0:
            continue
        if check[i] == -1:
            check[i]=1
            stack.append(i)
            count2 += 1

sa = count1+count2+2-n

if count1+sa%2-count2>0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n=int(input())
 
root = [[] for i in range(n)]
for _ in range(n-1):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

stack=[0]
check = [-1]*n
check[0] = 0
count1 = 0
while len(stack):
    v = stack.pop()
    for i in root[v]:
        if i == n-1:
            continue
        if check[i] == -1:
            check[i]=1
            stack.append(i)
            count1 += 1

stack=[n-1]
check = [-1]*n
check[n-1] = 0
count2 = 0
while len(stack):
    v = stack.pop()
    for i in root[v]:
        if i == 0:
            continue
        if check[i] == -1:
            check[i]=1
            stack.append(i)
            count2 += 1


if count1-count2>0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n=int(input())
 
root = [[] for i in range(n)]
for _ in range(n-1):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

stack=[0]
check = [-1]*n
check[0] = 0
count1 = 0
while len(stack):
    v = stack.pop()
    for i in root[v]:
        if i == n-1:
            continue
        if check[i] == -1:
            check[i]=1
            stack.append(i)
            count1 += 1

stack=[n-1]
check = [-1]*n
check[n-1] = 0
count2 = 0
while len(stack):
    v = stack.pop()
    for i in root[v]:
        if i == 0:
            continue
        if check[i] == -1:
            check[i]=1
            stack.append(i)
            count2 += 1


if count1-count2>=0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n=int(input())
 
root = [[] for i in range(n)]
for _ in range(n-1):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

stack=[0]
check = [-1]*n
check[0] = 0
count = 0
while len(stack):
    v = stack.pop()
    for i in root[v]:
        if i == n-1:
            continue
        if check[i] == -1:
            check[i]=1
            stack.append(i)
            count += 1

if count>n-2-count:
    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(lambda x: int(x) - 1,input().split())
    G[a].append(b)
    G[b].append(a)

dist_zero = [-1]*n
dist_zero[0] = 0
queue = deque()
queue.append(0)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist_zero[to] == -1:
            dist_zero[to] = dist_zero[now] + 1
            queue.append(to)

dist_n = [-1]*n
dist_n[-1] = 0
queue = deque()
queue.append(-1)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist_n[to] == -1:
            dist_n[to] = dist_n[now] + 1
            queue.append(to)

f = sum([(dist_zero[i]<=dist_n[i]) for i in range(n)])
print(f)
print("Fennec" if 2*f > n 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(lambda x: int(x) - 1,input().split())
    G[a].append(b)
    G[b].append(a)

dist_zero = [-1]*n

dist_zero[0] = 0
queue = deque()
queue.append(0)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist_zero[to] == -1:
            dist_zero[to] = dist_zero[now] + 1
            queue.append(to)

dist_n = [-1]*n
dist_n[-1] = 0
queue = deque()
queue.append(-1)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist_n[to] == -1:
            dist_n[to] = dist_n[now] + 1
            queue.append(to)

f = sum([(dist_zero[i]<=dist_n[i]) for i in range(n)])
print("Fennec" if 2*f >= n else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

data = [[] for i in range(N)]

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

stack = deque([0])
visit_in = [-1]*N
visit_in[0] = 0

while stack:
    x = stack.pop()
    for y in data[x]:
        if visit_in[y] >= 0:
            continue
        visit_in[y] = x
        stack.append(y)

path = [N-1]

while path[-1] != 0:
    path.append(visit_in[path[-1]])

#print(path)

group = [-1]*N

for x in path:
    group[x] = x

stack = deque(path[:])

while stack:
    x = stack.pop()
    for y in data[x]:
        if group[y] != -1:
            continue
        group[y] = group[x]
        stack.append(y)

#print(group)

num = [0]*N
for i in range(N):
    num[group[i]] += 1

#print(num)

p = len(path)-1
q = 0
fennec = num[0]
snuke = num[N-1]
while q < p - 1:
    p -= 1
    fennec += num[path[p]]
    if q < p:
        q += 1
        snuke += num[path[q]]

if fennec <= snuke:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

data = [[] for i in range(N)]

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

stack = deque([0])
visit_in = [-1]*N
visit_in[0] = 0

while stack:
    x = stack.pop()
    for y in data[x]:
        if visit_in[y] >= 0:
            continue
        visit_in[y] = x
        stack.append(y)

path = [N-1]

while path[-1] != 0:
    path.append(visit_in[path[-1]])

#print(path)

group = [-1]*N

for x in path:
    group[x] = x

stack = deque(path[:])

while stack:
    x = stack.pop()
    for y in data[x]:
        if group[y] != -1:
            continue
        group[y] = group[x]
        stack.append(y)

#print(group)

num = [0]*N
for i in range(N):
    num[group[i]] += 1

#print(num)

p = len(path)-1
q = 0
fennec = num[0]
snuke = num[N-1]
while q < p:
    p -= 1
    fennec += num[p]
    if q < p:
        q += 1
        snuke += num[q]

if fennec <= snuke:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

data = [[] for i in range(N)]

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

stack = deque([0])
visit_in = [-1]*N
visit_in[0] = 0

while stack:
    x = stack.pop()
    for y in data[x]:
        if visit_in[y] >= 0:
            continue
        visit_in[y] = x
        stack.append(y)

path = [N-1]

while path[-1] != 0:
    path.append(visit_in[path[-1]])

#print(path)

group = [-1]*N

for x in path:
    group[x] = x

stack = deque(path[:])

while stack:
    x = stack.pop()
    for y in data[x]:
        if group[y] != -1:
            continue
        group[y] = group[x]
        stack.append(y)

#print(group)

num = [0]*N
for i in range(N):
    num[group[i]] += 1

#print(num)

p = len(path)-1
q = 0
fennec = num[0]
snuke = num[N-1]
while q < p:
    q += 1
    fennec += num[q]
    if q < p:
        p -= 1
        snuke += num[p]

if fennec <= snuke:
    print("Snuke")
else:
    print("Fennec")