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())

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 = 0
q = len(path)-1
fennec = num[0]
snuke = num[N-1]
while p < q:
    p += 1
    fennec += num[p]
    if p < q:
        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 = 0
q = len(path)-1
fennec = num[0]
sunuke = num[N-1]
while p < q:
    p += 1
    fennec += num[p]
    if p < q:
        q -= 1
        sunuke += num[q]

if fennec <= sunuke:
    print("Sunuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

print(link)
from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=1
prev=[-1]*n

while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=1
        Q.append(nxt)
        prev[nxt]=now

rt=[n-1]
now=n-1
while prev[now]!=-1:
    now=prev[now]
    rt.append(now)
rt.reverse()
cut= -(-len(rt)//2)
f_node=rt[cut-1]
s_node=rt[cut]

Q = deque()
Q.append([0,0]) # 0 is f, 1 if s
visited=[-1]*n
visited[0]=0

while Q:
    now,fs = Q.popleft()
    for nxt in link[now]:
        nxt_fs=fs
        if now==f_node and nxt==s_node:
            nxt_fs=1
        if visited[nxt]!=-1:
            continue
        visited[nxt]=nxt_fs
        Q.append([nxt,nxt_fs])
s_score = sum(visited)
f_score = n-s_score
if s_score >= f_score:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

print(link)
from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=1
prev=[-1]*n

while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=1
        Q.append(nxt)
        prev[nxt]=now

rt=[n-1]
now=n-1
while prev[now]!=-1:
    now=prev[now]
    rt.append(now)
rt.reverse()
cut= -(-len(rt)//2)
f_node=rt[cut-1]
s_node=rt[cut]

Q = deque()
Q.append([0,0]) # 0 is f, 1 if s
visited=[-1]*n
visited[0]=0

while Q:
    now,fs = Q.popleft()
    for nxt in link[now]:
        nxt_fs=fs
        if now==f_node and nxt==s_node:
            print("fs=1")
            nxt_fs=1
        if visited[nxt]!=-1:
            continue
        visited[nxt]=nxt_fs
        Q.append([nxt,nxt_fs])
s_score = sum(visited)
f_score = n-s_score
if s_score >= f_score:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=1
prev=[-1]*n

while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=1
        Q.append(nxt)
        prev[nxt]=now

rt=[n-1]
now=n-1
while prev[now]!=-1:
    now=prev[now]
    rt.append(now)
rt.reverse()
cut= -(-len(rt)//2)
f_node=rt[cut-1]
s_node=rt[cut]
Q = deque()
Q.append([0,0]) # 0 is f, 1 if s
visited=[-1]*n
visited[0]=0

while Q:
    now,fs = Q.popleft()
    for nxt in link[now]:
        if now==f_node and nxt==s_node:
            fs=1
        if visited[nxt]!=-1:
            continue
        visited[nxt]=fs
        Q.append([nxt,fs])
s_score = sum(visited)
f_score = n-s_score
if s_score >= f_score:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(200000)
lf,ls=[None]*N,[None]*N
lf[0]=0
ls[-1]=0
def hu(n,c,l):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            hu(i,c+1,l)
hu(0,1,lf)
hu(-1,1,ls)
af=0
for i in range(N):
    if lf[i]<ls[i]:
        af+=1
if af*2>=N:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(i, c):
    q = deque()
    q.append(i)
    while q:
        p = q.popleft()
        for j in g[p]:
            if c[j] == 0 and i != j:
                q.append(j)
                c[j] = c[p] + 1
    return c

n = int(input())
g = [-1] * n
c1 = [0] * n
c2 = [0] * n
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if g[a] == -1:
        g[a] = [b]
    else:
        g[a].append(b)
    if g[b] == -1:
        g[b] = [a]
    else:
        g[b].append(a)

c1 = bfs(0, c1)
c2 = bfs(n - 1, c2)

F, S = 0, 0
for i in range(n):
    if c1[i] <= c2[i]:
        F += 1
    else:
        S += 1
print("Fennec" if F >= S else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
            union_count[root_s] += union_count[root_t]
        elif rank[s] > rank[t]:
            root[root_t] = root_s
            union_count[root_s] += union_count[root_t]
        else:
            root[root_s] = root_t
            union_count[root_t] += union_count[root_s]

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

def dfs(i, j):
    q = deque()
    q.append(i)
    p = i
    while q:
        u = g[p]
        v = c[p]
        if sum(v) == len(v):
            p = q.pop()
        u = g[p]
        v = c[p]   
        for k in range(len(u)):
            if v[k] == 0:
                if not u[k] in q:
                    q.append(u[k])
                    p = u[k]
                    v[k] = 1
                    break
                else:
                    v[k] = 1
        if p == j:
            return q

n = int(input())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
union_count = [1 for _ in range(n)]
t = [list(map(int, input().split())) for _ in range(n - 1)]
g = [-1] * (n + 1)
c = [-1] * (n + 1)
for s in t:
    if g[s[0]] == -1:
        g[s[0]] = [s[1]]
        c[s[0]] = [0]
    else:
        g[s[0]].append(s[1])
        c[s[0]].append(0)
    if g[s[1]] == -1:
        g[s[1]] = [s[0]]
        c[s[1]] = [0]
    else:
        g[s[1]].append(s[0])
        c[s[1]].append(0)
q = dfs(1, n)
if len(q) % 2 == 0:
    a, b = q[len(q) // 2 - 1], q[len(q) // 2]
else:
    a, b = q[len(q) // 2], q[len(q) // 2 + 1]
for s in t:
    if s != [a, b] and s != [b, a]:
        unite(s[0] - 1, s[1] - 1)
F = union_count[get_root(0)]
S = union_count[get_root(n - 1)]
if F > S:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from collections import deque

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

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

for e in E:
    tree[e[0] - 1].append(e[1] - 1)
    tree[e[1] - 1].append(e[0] - 1)

color = [None for _ in range(N)]
color[0] = 0
color[N - 1] = 1

fennec = deque([0])
snuke = deque([N - 1])

while fennec or snuke:
    if fennec:
        node = fennec.popleft()
        for adj in tree[node]:
            if color[adj] is None:
                color[adj] = 0
                fennec.append(adj)
    if snuke:
        node = snuke.popleft()
        for adj in tree[node]:
            if color[adj] is None:
                color[adj] = 1
                snuke.append(adj)

if N - sum(color) > sum(color):
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
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)

INF=10**9

d=[INF for i in range(N)]
edges=[0 for i in range(N)]
d[0]=0
queue=[]
queue.append(0)

while queue:
    u=queue.pop(0)
    for i in range(len(G[u])):
        if d[G[u][i]]==INF:
            queue.append(G[u][i])
            d[G[u][i]]=d[u]+1

k=d[N-1]
m=N-1
queue.append(N-1)

while k>d[N-1]//2+1:
    u=queue.pop(0)
    for i in range(len(G[u])):
        if d[G[u][i]]==d[u]-1:
            queue.append(G[u][i])
            k=d[G[u][i]]
            m=u

queue=[]
queue.append(m)
unused=[True for i in range(N)]
unused[m]=False

sunuke=1

while queue:
    u=queue.pop(0)
    sunuke+=len(G[u])-1
    for i in range(len(G[u])):
        if d[G[u][i]]>d[u] and unused[G[u][i]]:
            queue.append(G[u][i])
            unused[G[u][i]]=False

if sunuke>=-(-N//2):
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

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

steps = [-99 for _ in range(N)]
steps[0] = 0
isVisited = [False for _ in range(N)]
toSearch = deque([0, ])
isVisited[0] = True
while len(toSearch) > 0:
    nowP = toSearch.pop()
    nowStep = steps[nowP]
    if nowP == N-1:
        break
    for nextP in path[nowP]:
        if not isVisited[nextP]:
            isVisited[nextP] = True
            toSearch.appendleft(nextP)
            steps[nextP] = nowStep + 1

fennecLength = ((nowStep-1)+1)//2

snukePoint = 0
isVisited = [False for _ in range(N)]
toSearch = deque([N-1, ])
isVisited[N-1] = True
while len(toSearch) > 0:
    nowP = toSearch.pop()
    snukePoint += 1
    nowStep = steps[nowP]
    # To FIX break condition
    if nowStep == fennecLength:
        snukePoint -= 1
        continue
    for nextP in path[nowP]:
        if not isVisited[nextP]:
            isVisited[nextP] = True
            toSearch.appendleft(nextP)
if snukePoint >= N-2:
    print("Snuke")
else:
    print("Fennec")
#print(snukePoint)
#print(steps)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
adj = [[] for i in range(N)]


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


dq = deque([(0, 'b'), (N-1, 'w')])

colors = [0] * N
colors[0] = 'b'
colors[-1] = 'w'


while dq:
    node, color = dq.pop()
    for dest in adj[node]:
        if colors[dest] != 0:
            continue
        else:
            colors[dest] = color
            dq.append((dest, color))

print('Fennec' if colors.count('b') > N//2 else 'Snuke')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import queue

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    dL=[[0,0] for _ in range(N)]
    
    q=queue.Queue()
    
    #0からの距離
    for j in range(2):
        if j==0:
            q.put((0,0,0))#v,pare,d
        else:
            q.put((N-1,N-1,0))#v,pare,d
        while not q.empty():
            v,p,d=q.get()
            for i in range(len(adj[v])):
                nv=adj[v][i]
                if nv!=p:
                    dL[v][j]=d
                    q.put((nv,v,d+1))
                    
    s=0
    for i in range(N):
        if dL[i][0]>dL[i][1]:
            s+=1
    
        
    
    if s>=N-s:
        print("Snuke")
    else:
        print("Fennec")
     
        
    
    

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import queue

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    bit=[0]*N
    
    q=queue.Queue()
    q.put([0,0,0])#v.pare,depth
    
    while not q.empty():
        v,p,d=q.get()
        if v==N-1:
            bit[v]=1
        else:
            bit[v]=bit[p]
        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q.put((nv,v,d+1))
                    
    s=sum(bit)#sunukeが塗れる
    if s>=N-s:
        print("Snuke")
    else:
        print("Fennec")
     
        
    
    

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

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

# BFS
def dist_from_X(X:int):
    dist = np.full(N, -1)
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for e in E[v]:
            if dist[e] > -1:
                continue
            dist[e] = d + 1
            que.append(e)
    return dist

Fennec = dist_from_X(0)
Sunuke = dist_from_X(N-1)

cnt = np.count_nonzero(Fennec <= Sunuke)

if cnt > N - cnt:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

tree = [[] for i in range(n)]

dp0 = [0 for i in range(n)]
dp1 = [0 for i in range(n)]

dp0[0] = 1
dp1[-1] = 1

for i in range(n-1):
    o,p = m()
    o -= 1
    p -= 1
    tree[o].append(p)
    tree[p].append(o)

de = cl.deque([0,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp0[i] == 0:
            dp0[i] = co
            de.append(i)

de = cl.deque([n-1,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp1[i] == 0:
            dp1[i] = co
            de.append(i)

dp0[0] = 0
dp1[-1] = 0

co = 0

for i in range(n):
    co += 1 if dp0[i] - dp1[i] <= 0 else -1
if co >= 0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

tree = [[] for i in range(n)]

dp0 = [0 for i in range(n)]
dp1 = [0 for i in range(n)]

dp0[0] = 1
dp1[-1] = 1

for i in range(n-1):
    o,p = m()
    o -= 1
    p -= 1
    tree[o].append(p)
    tree[p].append(o)

de = cl.deque([0,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp0[i] == 0:
            dp0[i] = co
            de.append(i)

de = cl.deque([n-1,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp1[i] == 0:
            dp1[i] = co
            de.append(i)

dp0[0] = 0
dp1[-1] = 0

co = 0

for i in range(n):
    co -= 1 if dp0[i] - dp1[i] > 0 else -1
if co >= 0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

tree = [[] for i in range(n)]

dp0 = [0 for i in range(n)]
dp1 = [0 for i in range(n)]

dp0[0] = 1
dp1[-1] = 1

for i in range(n-1):
    o,p = m()
    o -= 1
    p -= 1
    tree[o].append(p)
    tree[p].append(o)

de = cl.deque([0,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp0[i] == 0:
            dp0[i] = co
            de.append(i)

de = cl.deque([n-1,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp1[i] == 0:
            dp1[i] = co
            de.append(i)

dp0[0] = 0
dp1[-1] = 0

co = 0

for i in range(n):
    co -= 1 if dp0[i] - dp1[i] >= 0 else -1
if co >= 0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# BFS
def dist_from_X(X):
    dist = [-1] * N
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.pop()
        d = dist[v]
        for e in E[v]:
            if dist[e] > -1:
                continue
            dist[e] = d + 1
            que.append(e)
    return dist

Fennec = dist_from_X(0)
Sunuke = dist_from_X(N-1)

cnt = [0,0]
for i,j in zip(Fennec, Sunuke):
    if i <= j:
        cnt[0] += 1
    else:
        cnt[1] += 1

# cnt[0] == cnt[1]の場合、後手勝利
if cnt[0] > cnt[1]:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# BFS
def dist_from_X(X):
    dist = [-1] * N
    
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for e in E[v]:
            if dist[e] > -1:
                continue
            dist[e] = d + 1
            que.append(e)
    
    return dist

Fennec = dist_from_X(0)
Sunuke = dist_from_X(N-1)

cnt = [0,0]
for i,j in zip(Fennec, Sunuke):
    if i <= j:
        cnt[0] += 1
    else:
        cnt[1] += 1

# cnt[0] == cnt[1]の場合、後手勝利
if cnt[0] > cnt[1]:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ 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)
#print(g)

from collections import deque
q = deque()
visit = [-1]*n
q.append(0)
visit[0] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if visit[new_x] != -1:
            continue
        visit[new_x] = visit[x]+1
        q.append(new_x)
        #if new_x == n-1:
            #break
#print(visit)

q = deque()
visit2 = [-1]*n
q.append(n-1)
visit2[n-1] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if visit2[new_x] != -1:
            continue
        visit2[new_x] = visit2[x]+1
        q.append(new_x)
#print(visit2)

fe = 0
sn = 0
for i in range(n):
    if visit[i] <= visit2[i]:
        fe += 1
    else:
        sn += 1
if fe >= sn:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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


def dist(root):  # 根をnとしたときの各点の深さ
    res = [-1] * (N + 1)
    node = [root]
    res[root] = 0
    while node:
        s = node.pop()
        d = res[s]
        for t in edge[s]:
            if res[t] == -1:
                node.append(t)
                res[t] = d + 1
    return res


fenek = dist(1)
snuke = dist(N)
f, s = 0, 0
for i, j in zip(fenek, snuke):
    if i <= j:
        f += 1
    else:
        s += 1

ans = "Fennec" if f > s else "Snuke"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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


def dist(root):  # 根をnとしたときの各点の深さ
    res = [-1] * (N + 1)
    node = [root]
    res[root] = 0
    while node:
        s = node.pop()
        d = res[s]
        for t in edge[s]:
            if res[t] == -1:
                node.append(t)
                res[t] = d + 1
    return res[1:]


fenek = dist(1)
snuke = dist(N)
f, s = 0, 0
for i in range(2, N):
    if fenek[i] <= snuke[i]:
        f += 1
    else:
        s += 1

ans = "Fennec" if f > s else "Snuke"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def shortest_path(pt,s,t):
    n = len(pt)
    used = [False]*n
    pre = [-1]*n
    q = [s]
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if not used[j]:
                    used[j] = True
                    pre[j] = i
                    q1.append(j)
        q = q1

    if used[t]:
        path = [t]
        p = t
        while True:
            p = pre[p]
            path.append(p)
            if p == s:
                break
        return list(reversed(path))
    else:
        return []

N = I()
a,b = MI(N-1,2)

pt = edges_to_pt(a,b,N)
path = shortest_path(pt,0,N-1)

v = path[math.ceil(len(path)/2)]
visited = [False]*N
visited[v] = True
S = [v]
num = 1
while S:
    v1 = S.pop()
    if v1 == path[math.ceil(len(path)/2)-1]:
        continue
    for i in pt[v1]:
        if not visited[i]:
            visited[i] = True
            num += 1
            S.append(i)

if N-num > num:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
N=int(input())
AB=[map(int,input().split()) for i in range(N-1)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
stack=deque([[1,0]])
visited=set([1])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        if p==N:
            break
        if not p in visited:
            visited.add(a)
            stack.append([p,m+1])
M=m//2
countFennec=0
countSnuke=0
visited=set([1,N])
stackSnuke=deque([[N,0]])
while stackSnuke:
    a,m=stackSnuke.popleft()
    if m>=M:
        stackSnuke.append([a,m])
        break
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(a)
            stack.append([p,m+1])

stackFennec=deque([[1,0]])
while stackFennec:
    a,m=stackFennec.popleft()
    for p in data[a]:
        if not p in visited:
            countFennec+=1
            visited.add(a)
            stack.append([p,m+1])

while stackSnuke:
    a,m=stackSnuke.popleft()
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(a)
            stack.append([p,m+1])

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

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
N=int(input())
AB=[map(int,input().split()) for i in range(N-1)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
stack=deque([[1,0]])
visited=set([1])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        if p==N:
            break
        if not p in visited:
            visited.add(a)
            stack.append([p,m+1])
M=m//2
countFennec=0
countSnuke=0
visited=set([1,N])
stackSnuke=deque([[N,0]])
while stackSnuke:
    a,m=stackSnuke.popleft()
    if m>=M:
        stack.append([a,m])
        break
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(a)
            stack.append([p,m+1])

stackFennec=deque([[1,0]])
while stackFennec:
    a,m=stackFennec.popleft()
    for p in data[a]:
        if not p in visited:
            countFennec+=1
            visited.add(a)
            stack.append([p,m+1])

while stackSnuke:
    a,m=stackSnuke.popleft()
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(a)
            stack.append([p,m+1])

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

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
N=int(input())
AB=[map(int,input().split()) for i in range(N-1)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
stack=deque([[1,0]])
visited=set([1])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        if p==N:
            break
        if not p in visited:
            visited.add(a)
            stack.append([p,m+1])
M=m//2
countFennec=0
countSnuke=0
visited=set([1,N])
stackSnuke=deque([[N,0]])
while stackSnuke:
    a,m=stackSnuke.popleft()
    if m>=M:
        break
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(a)
            stack.append([p,m+1])

stackFennec=deque([[1,0]])
while stackFennec:
    a,m=stackFennec.popleft()
    for p in data[a]:
        if not p in visited:
            countFennec+=1
            visited.add(a)
            stack.append([p,m+1])

while stackSnuke:
    a,m=stackSnuke.popleft()
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(a)
            stack.append([p,m+1])

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