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())
T = [[] for _ in range(N)]


def dfs(k):
    q = [k]
    d = [-1] * N
    d[k] = 0
    while len(q) > 0:
        v = q.pop()
        for i in T[v]:
            if d[i] == -1:
                d[i] = d[v] + 1
                q.append(i)
    return d


def main():
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        T[a].append(b)
        T[b].append(a)
    c = dfs(0)
    d = dfs(N - 1)
    ac = 0
    for x, y in zip(c, d):
        if y > x:
            ac += 1
    if ac > N // 2:
        print('Fennec')
    else:
        print('Snuke')


main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    es[a].append(b)
    es[b].append(a)
pre = [None] * (N+1)
pre[1] = 0
dq = deque()
dq.append((0, 1))
while dq:
    d, v = dq.popleft()
    if v == N:
        break
    for u in es[v]:
        if pre[u] == None:
            pre[u] = v
            dq.append((d+1, u))
col = [None] * (N+1)
v = N
sv = [N]
for i in range(d+1):
    if i < d/2:
        col[v] = 0
    else:
        col[v] = 1
    v = pre[v]
    sv.append(v)
bc, wc = 0, 0
for s in sv:
    dq = deque()
    dq.append(s)
    c = 0
    while dq:
        v = dq.popleft()
        c += 1
        for u in es[v]:
            if col[u] == None:
                col[u] = col[s]
                dq.append(u)
    if col[s] == 1:
        bc += c
    else:
        wc += c
if bc > wc:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import bisect
from operator import itemgetter
import math
import copy
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x):
    global f
    if visited[x] == False:
        visited[x] = True
        path.append(x)
        if x == N:
            f = 1
        else:
            for i in root[x]:
                tami(i)
            if f == 0:
                del path[-1]

def nas(x):
    global cnt
    if (visited[x] == False) and (data[x] == 0):
        visited[x] = True
        cnt += 1
        for i in root[x]:
            nas(i)

N = I()
ab = [IL() for i in range(N-1)]
data = np.array([0]*(N+1))
root = [[]*(N+1) for i in range(N+1)]
visited = [False]*(N+1)

path = []
f = 0
for a,b in ab:
    root[a].append(b)
    root[b].append(a)

tami(1)
middle_No = path[math.ceil(len(path)/2)-1]
data[middle_No] = 1

visited = [False]*(N+1)
cnt = 0
nas(N)

Snuke = cnt
Fennec = N - Snuke

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

Submission status: Wrong Answer

Solution code:
import bisect
from operator import itemgetter
import math
import copy
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x):
    global f
    if visited[x] == False:
        visited[x] = True
        path.append(x)
        if x == N:
            f = 1
        else:
            for i in root[x]:
                tami(i)
            if f == 0:
                del path[-1]

def nas(x):
    global cnt
    if (visited[x] == False) and (data[x] == 0):
        visited[x] = True
        cnt += 1
        for i in root[x]:
            nas(i)

N = I()
ab = [IL() for i in range(N-1)]
data = np.array([0]*(N+1))
root = [[]*(N+1) for i in range(N+1)]
visited = [False]*(N+1)

path = []
f = 0
for a,b in ab:
    root[a].append(b)
    root[b].append(a)

tami(1)
middle_No = path[len(path)//2]
data[middle_No] = 1

visited = [False]*(N+1)
cnt = 0
nas(1)

if middle_No != N:
    cnt += 1

Fennec = cnt
Snuke = N - Fennec

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

Submission status: Wrong Answer

Solution code:
import queue

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

T = {}
for a, b in ab:
  if a not in T:
    T[a] = [b]
  else:
    T[a].append(b)
  if b not in T:
    T[b] = [a]
  else:
    T[b].append(a)

R = [-1] * (N + 1)
q = queue.Queue()
put = q.put
get = q.get
put(1)
R[1] = 1
while not q.empty(): 
  t = get()
  if t in T:
    for i in T[t]:
      if R[i] == -1:
        R[i] = R[t] + 1
        put(i)

L = [N]
t = N
while t != 1:
  for i in T[t]:
    if R[i] < R[t]:
      L.append(i)
      t = i
      break

k = L[len(L) // 2 - 1]

cnt = 1
put(k)
while not q.empty(): 
  t = get()
  if t in T:
    for i in T[t]:
      if R[i] > R[t]:
        cnt += 1
        put(i)

Ans = ["Fennec", "Snuke"]
print(Ans[cnt > N - cnt])

Submission status: Wrong Answer

Solution code:
import queue

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

T = {}
for a, b in ab:
  if a not in T:
    T[a] = [b]
  else:
    T[a].append(b)
  if b not in T:
    T[b] = [a]
  else:
    T[b].append(a)

R = [-1] * (N + 1)
q = queue.Queue()
put = q.put
get = q.get
put(1)
R[1] = 1
while not q.empty(): 
  t = get()
  if t in T:
    for i in T[t]:
      if R[i] == -1:
        R[i] = R[t] + 1
        put(i)

L = [N]
t = N
while t != 1:
  for i in T[t]:
    if R[i] < R[t]:
      L.append(i)
      t = i
      break

k = L[len(L) // 2 - 1]

cnt = 1
put(k)
while not q.empty(): 
  t = get()
  if t in T:
    for i in T[t]:
      if R[i] > R[t]:
        cnt += 1
        put(i)
print(cnt)
Ans = ["Fennec", "Snuke"]
print(Ans[cnt > N - cnt])

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/abc067/submissions/1562911
#コピペコード
N = int(input())
ab = [[] for i in range(N+1)]
for i in range(N-1):              #隣接リスト作成
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
 
def calc_dist(K):
    # dist[i]:頂点Kから頂点iまでの距離
    dist = [-1 for i in range(N+1)]
    dist[K] = 0
 
    # 深さ優先探索（スタック）
    from collections import deque
    stack = deque()
    stack.append(K)
 
    while stack:
        v = stack.pop()
        for nxt in ab[v]:            #隣接リストから値をとっていく
            if dist[nxt] == -1:
                dist[nxt] = dist[v] + 1
                stack.append(nxt)
 
    return dist
 
dist1 = calc_dist(1)
distN = calc_dist(N)
 
Fennec = 0
Snuke = 0
for v in range(N):
    if dist1[v] <= distN[v]:     #vまで行くのにどちらが早いか
        Fennec += 1
    else:
        Snuke += 1
 
if Fennec > Snuke:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
g = [[] for _ in range(N + 1)]
gtf = [False] * (N+1)
gtf[1] = True
gtf[-1] = True
finish = False
win = ""
for a, b in ab:
    g[a].append(b)
    g[b].append(a)
now_f = 1
now_s = N
while win == "":
    next_f = -1
    next_s = -1
    for i in g[now_f]:
        if not gtf[i]:
            next_f = max(next_f, len(g[i]))
    for j in g[now_s]:
        if not gtf[i]:
            next_s = max(next_s, len(g[j]))
    if next_f == -1:
        win = "Snuke"
        break
    if next_s == -1:
        win = "Fennec"
        break    
    now_f = next_f
    now_s = next_s
print(win)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
d={}
for i in range(n-1):
    #a,b=map(int,input().split()) ?str spd?
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
    if b in d:
        d[b].append(a)
    else:
        d[b]=[a]
f,s=set([]),set([])
e=deque([1])
u=deque([n])
x=0
while 1:
    if x==1 and e[-1]==1:
        break
    x=1
    t=e.pop()
    for i in d[t]:
        if i!=1 and i not in f and i!=n:
            f.add(i)
            e.append(i)
    e.appendleft(t)
x=0
while 1:
    if x==1 and u[-1]==n:
        break
    x=1
    t=u.pop()
    for i in d[t]:
        if i!=n and i not in s and i!=1:
            s.add(i)
            u.append(i)
    u.appendleft(t)
p=len(f-s)
q=len(s-f)
r=len(f&s)
p+=r%2
print(["Fennec","Snuke"][p<=q])

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
d={}
for i in range(n-1):
    #a,b=map(int,input().split()) ?str spd?
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
    if b in d:
        d[b].append(a)
    else:
        d[b]=[a]
f,s=set([]),set([])
e=deque([1])
u=deque([n])
x=0
while 1:
    if x==1 and e[-1]==1:
        break
    x=1
    t=e.pop()
    for i in d[t]:
        if i!=1 and i not in f and i!=n:
            f.add(i)
            e.append(i)
    e.appendleft(t)
x=0
while 1:
    if x==1 and u[-1]==n:
        break
    x=1
    t=u.pop()
    for i in d[t]:
        if i!=n and i not in s and i!=1:
            s.add(i)
            u.append(i)
    u.appendleft(t)
p=len(f-s)
q=len(s-f)
r=len(f&s)
p+=r%2
print(["Fennec","Sunuke"][p<=q])

Submission status: Wrong Answer

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


def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num - 1)]
    graph_data = defaultdict(set)
    for i in range(num - 1):
        a, b = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)

    black, white = 0, 0
    b_ind_now, w_ind_now = set(), set()
    b_ind_next, w_ind_next = set(), set()
    # b_ind_pre, w_ind_pre = set(), set()
    pre_ind = set()
    b_ind_now.add(1)
    w_ind_now.add(1)
    # b_ind_pre.add(1)
    # w_ind_pre.add(1)
    pre_ind.add(1)
    pre_ind.add(num)

    while len(b_ind_now) > 0 or len(w_ind_now) > 0:
        for ele_now in b_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                b_ind_next.add(ele_next)
                black += 1
        b_ind_now = b_ind_next
        b_ind_next = set()


        for ele_now in w_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                w_ind_next.add(ele_next)
                white += 1
        w_ind_now = w_ind_next
        w_ind_next = set()

    if black > white:
        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())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
stack1=deque(G[0])
stack2=deque(G[N-1])
X=[-1]*N
X[0]=1
X[N-1]=0
while(stack1 or stack2):
    Stack1=deque()
    for i in stack1:
        if X[i]==-1:
            X[i]=1
            for j in G[i]:
                if X[j]==-1:
                    Stack1.append(j)
    stack1=Stack1
    Stack2=deque()
    for i in stack2:
        if X[i]==-1:
            X[i]=0
            for j in G[i]:
                if X[j]==-1:
                    Stack2.append(j)
    stack2=Stack2
f,s=0,0
for i in range(N):
    if X[i]==1:
        f+=1
    else:
        s+=1
if f>s:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)


#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0

N=int(input())
par = [-1]*N
wei = [0]*N
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    unite(a,b,1)
f=0
s=0
for i in range(N):
    if abs(diff(0,i))<=abs(diff(N-1,i)):
        f+=1
    else:
        s+=1
if f>s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return abs(weight(y)-weight(x))


#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0

N=int(input())
par = [-1]*N
wei = [0]*N
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    unite(a,b,1)
f=0
s=0
for i in range(N):
    if diff(0,i)<=diff(N-1,i):
        f+=1
    else:
        s+=1
if f>s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)


#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0

N=int(input())
par = [-1]*N
wei = [0]*N
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    unite(a,b,1)
f=0
s=0
for i in range(N):
    if diff(0,i)<=diff(N-1,i):
        f+=1
    else:
        s+=1
if f>s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)


#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0

N=int(input())
par = [-1]*N
wei = [0]*N
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    unite(a,b,1)
f=0
s=0
for i in range(N):
    if diff(0,i)<=diff(N-1,i):
        f+=1
    else:
        s+=1
if f>s:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)
    def find_path(idx, target, conn, visited):
        visited[idx] = True
        if idx == target:
            return [target]
        for nex in conn[idx]:
            if not visited[nex]:
                path = find_path(nex, target, conn, visited)
                if path is not None:
                    return [idx] + path
        return None

    visited = [False] * N
    path_to_n = find_path(0, N - 1, conn, visited)
    #print(path_to_n)

    colors = [None] * N
    for i, node in enumerate(path_to_n):
        if i < (len(path_to_n) + 1) / 2:
            colors[node] = True
        else:
            colors[node] = False

    def dfs(idx, conn, colors):
        colors[idx] = True
        for nex in conn[idx]:
            if colors[nex] is None:
                dfs(nex, conn, colors)
        return

    cnt = 0
    dfs(0, conn, colors)
    #print(colors)
    for c in colors:
        if c:
            cnt += 1
    if cnt > (N - cnt):
        ret = 'Fennec'
    else:
        ret = 'Snuke'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
G =[[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
dist1 = [0]*(N+1)
def func1(now, prv, d):
    dist1[now] = d
    for p in G[now]:
        if p != prv:
            func1(p, now, d+1)
func1(1, 0, 0)

fen = 0
sun = 0
d = dist1[N]
d1 = d//2
for i in range(1, N+1):
    if dist1[i] <= d1:
        fen += len(G[i])
        fen -= 1
fen += 1
sun = N-fen
if fen > sun:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
G =[[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
dist1 = [0]*(N+1)
def func1(now, prv, d):
    dist1[now] = d
    for p in G[now]:
        if p != prv:
            func1(p, now, d+1)
func1(1, 0, 0)

fen = 0
sun = 0
d = dist1[N]
d1 = d//2
for i in dist1[1:]:
    if i <= d1:
        fen += 1
    else:
        sun += 1
if fen > sun:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = MI_()
        edge[a].append(b)
        edge[b].append(a)

    set_A = set()
    set_B = set()
    a_stack = [0]
    b_stack = [N - 1]
    for _ in range(N - 1):
        tmp_a = []
        tmp_b = []
        while a_stack:
            from_ = a_stack.pop()
            for to in edge[from_]:
                if to not in set_B:
                    tmp_a.append(to)
                    set_A.add(to)
        while b_stack:
            from_ = b_stack.pop()
            for to in edge[from_]:
                if to not in set_A:
                    tmp_b.append(to)
                    set_B.add(to)
    if len(set_A) >= len(set_B):
        print("Fennec")
    else:
        print("Snuke")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = MI_()
        edge[a].append(b)
        edge[b].append(a)

    set_A = set()
    set_B = set()
    a_stack = [0]
    b_stack = [N - 1]
    for _ in range(N - 1):
        tmp_a = []
        tmp_b = []
        while a_stack:
            from_ = a_stack.pop()
            for to in edge[from_]:
                if to not in set_B:
                    tmp_a.append(to)
                    set_A.add(to)
        while b_stack:
            from_ = b_stack.pop()
            for to in edge[from_]:
                if to not in set_A:
                    tmp_b.append(to)
                    set_B.add(to)
    if len(set_A) > len(set_B):
        print("Fennec")
    else:
        print("Snuke")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
Edges=[]
for i in range(n-1):
  a,b=map(int,input().split())
  Edges.append([a,b,1])
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
F,S=BFS(0,Edges,n),BFS(n-1,Edges,n)
count=0
for i in range(1,n-1):
  if F[i]<=S[i]:
    count+=1
  else:
    count-=1
print("Fennec" if count>=0 and n!=2 else "Snuke")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
Edges=[]
for i in range(n-1):
  a,b=map(int,input().split())
  Edges.append([a,b,1])
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
F,S=BFS(0,Edges,n),BFS(n-1,Edges,n)
count=0
for i in range(1,n-1):
  if F[i]<=S[i]:
    count+=1
  else:
    count-=1
print("Fennec" if count>=0 else "Snuke")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(114514)
N=int(input())
path=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b=map(int,input().split())
	path[a].append(b)
	path[b].append(a)
fenne=[-1 for _ in range(N+1)]
snuke=[-1 for _ in range(N+1)]
def walk(ar, i, d):
	if ar[i] == -1:
		ar[i] = d
		for x in path[i]:
			walk(ar, x, d+1)
walk(fenne, 1, 0)
walk(snuke, N, 0)
for i in range(1, N+1):
	if snuke[i] < fenne[i]:
		fenne[i] = -2
	else:
		snuke[i] = -2


print("Fennec" if max(fenne) > max(snuke) else "Snuke")

Submission status: Wrong Answer

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

adja_dict={}

for a,b in AB:
  adja_dict.setdefault(a, set()).add(b)
  adja_dict.setdefault(b, set()).add(a)

nodes = [None] * (N+2) #N[0]:b N[N+1]:w
nodes[0] = nodes[1] = 1
nodes[N] = nodes[N+1] = -1

queue = [1, N]
while queue:
  x = queue.pop()
  for y in adja_dict[x]:
    if nodes[y] is None:
      nodes[y] = nodes[x]
      queue.append(y)

if sum(nodes)>0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(start:int, goal:int):
    """print the shortet path  O(|E|log|V|)
    maybe verified
    """
    global dist # list dist[|V|]
    global edges # 隣接リスト
    dist[start] = 0
    prev_v = [-1]*(len(dist)) # 最短経路でのひとつ前の頂点
    q = [(0,start)] #（暫定的な距離，頂点）
    while q:
        d_cur,cur = heapq.heappop(q)
        if dist[cur] < d_cur: # すでに探索済み
            continue
        for nex,cost in edges[cur]:
            if dist[nex] > dist[cur]+cost:
                dist[nex] = dist[cur]+cost
                heapq.heappush(q, (dist[nex], nex))
                prev_v[nex] = cur

    # 以下 path の復元
    path = []
    v = goal
    while v != -1:
        path.append(v)
        v = prev_v[v]
    path = path[::-1] # reverse
    return path


if __name__ == "__main__":
    N = int(input())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,t = map(lambda x: int(x)-1, input().split())
        edges[s].append((t, 1))
        edges[t].append((s, 1))
    dist = [float('inf') for _ in range(N)]
    p = dijkstra(0, N-1)
    if len(p)==2:
        print("Snuke")
        exit()
    cut = (p[len(p)//2], p[len(p)//2+1])
    edges[cut[0]].remove((cut[1],1))
    edges[cut[1]].remove((cut[0],1))
    dist = [float('inf') for _ in range(N)]
    dijkstra(0, 0)
    f_score = 0
    for d in dist:
        if dist != float('inf'):
            f_score += 1
    print("Fennec" if f_score > N/2 else "Snuke")

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math
from collections import deque
from collections import defaultdict

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)       
    f= 0
    s= 0
    
    q = deque()
    q.append(1)
    d_from_1 = [-1]*(N+1)
    d_from_1[1] = 0
    i = 1
    while q:
        next_node = q.popleft()
        for succ in d[next_node]:
            if d_from_1[succ] == -1:
                d_from_1[succ] = i
                q.append(succ)
        i += 1
        
    q = deque()
    q.append(N)
    d_from_N = [-1]*(N+1)
    d_from_N[N] = 0
    i = 1
    q.append(N)
    while q:
        next_node = q.popleft()
        for succ in d[next_node]:
            if d_from_N[succ] == -1:
                d_from_N[succ] = i
                q.append(succ)
        i += 1
    # print(d_from_1)
    # print(d_from_N)
    for i in range(1,N+1):
        if(d_from_1[i] <= d_from_N[i]):
            f += 1
        else:
            s += 1
    if(f>s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()