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 defaultdict
import heapq
N = int(input())
graph = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]
is_visited = [False for i in range(N+1)]
q = []
heapq.heappush(q, (0, 0, 1))
t2f = {}
while q:
    c, f, t = heapq.heappop(q)
    t2f[t] = f
    if t == N:
        break
    for nt in graph[t]:
        if is_visited[nt]:
            continue
        heapq.heappush(q, (c+1, t, nt))
        is_visited[nt] = True
is_visited = [False for i in range(N+1)]
is_visited[N] = True
for i in range(c//2):
    f = t2f[t]
    is_visited[f] = True
    t = f
q = []
heapq.heappush(q, (0, 1))
ans = 0
while q:
    c, t = heapq.heappop(q)
    ans += 1
    for nt in graph[t]:
        if is_visited[nt]:
            continue
        heapq.heappush(q, (c+1, nt))
        is_visited[nt] = True
if N // 2 < ans:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq
N = int(input())
graph = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]
is_visited = [False for i in range(N+1)]
q = []
heapq.heappush(q, (0, 0, 1))
t2f = {}
while q:
    c, f, t = heapq.heappop(q)
    t2f[t] = f
    if t == N:
        break
    for nt in graph[t]:
        if is_visited[nt]:
            continue
        heapq.heappush(q, (c+1, t, nt))
        is_visited[nt] = True
is_visited = [False for i in range(N+1)]
is_visited[N] = True
for i in range(c//2):
    f = t2f[t]
    is_visited[f] = True
q = []
heapq.heappush(q, (0, 1))
ans = 0
while q:
    c, t = heapq.heappop(q)
    ans += 1
    for nt in graph[t]:
        if is_visited[nt]:
            continue
        heapq.heappush(q, (c+1, nt))
        is_visited[nt] = True
if N // 2 < ans:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq
N = int(input())
graph = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]
is_visited = [False for i in range(N+1)]
q = []
heapq.heappush(q, (0, 0, 1))
t2f = {}
while q:
    c, f, t = heapq.heappop(q)
    t2f[t] = f
    if t == N:
        break
    for nt in graph[t]:
        if is_visited[nt]:
            continue
        heapq.heappush(q, (c+1, t, nt))
        is_visited[nt] = True
is_visited = [False for i in range(N+1)]
is_visited[N] = True
for i in range(c//2):
    f = t2f[t]
    is_visited[f] = True
q = []
heapq.heappush(q, (0, 1))
ans = 0
while q:
    c, t = heapq.heappop(q)
    ans += 1
    for nt in graph[t]:
        if is_visited[nt]:
            continue
        heapq.heappush(q, (c+1, nt))
        is_visited[nt] = True
if N // 2 <= ans:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque

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


def bfs(G, root):
    n = len(G)
    Parents = [-1] * n
    Depth = [0] * n
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        for v in G[u]:
            if visited[v]:
                continue
            else:
                dq2 += [v]
                Depth[v] = Depth[u] + 1
                Parents[v] = u
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return Depth, Parents


Depth, Parents = bfs(Edge, 0)
cnt = (Depth[-1] - 1)//2
now = N-1
while cnt:
    cnt -= 1
    now = Parents[now]
Edge[Parents[now]].remove(now)

Q = deque()
Q.append(0)
Done = [0] * N
ans = 1
while Q:
    now = Q.popleft()
    for nex in Edge[now]:
        if Done[nex]:
            continue
        else:
            Q.append(nex)
            Done[nex] = 1
            ans += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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


def euler_tour(G, root):
    n = len(G)
    Parents = [-1] * n
    Depth = [0] * n
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        for v in G[u]:
            if visited[v]:
                continue
            else:
                dq2 += [v]
                Depth[v] = Depth[u] + 1
                Parents[v] = u
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return Depth, Parents


Depth, Parents = euler_tour(Edge, 0)
cnt = Depth[-1]//2
now = N-1
while cnt:
    cnt -= 1
    now = Parents[now]
Edge[Parents[now]].remove(now)

Q = deque()
Q.append(0)
Done = [0] * N
ans = 1
while Q:
    now = Q.popleft()
    for nex in Edge[now]:
        if Done[nex]:
            continue
        else:
            Q.append(nex)
            Done[nex] = 1
            ans += 1

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

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [set() for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].add(b-1)
    g[b-1].add(a-1)


def dfs(s, e):
    visited = [-1]*n
    visited[0] = 0
    cnt = 1
    temp = [[s, [0]]]
    lst = []
    while temp:
        p = temp.pop()
        for a in g[p[0]]:
            q = p[1][:]
            if visited[a] != -1:continue
            visited[a] = visited[p[0]] + 1
            q.append(a)
            if a == e: lst = q[:]
            temp.append([a, q])
            cnt += 1
    return cnt, lst

c0, lst = dfs(0, n-1)

m = (len(lst) - 1) // 2
g[lst[m]].discard(lst[m+1])
g[lst[m+1]].discard(lst[m])

c0, lst = dfs(0, n-1)

if c0 > n - c0: print('Fennec')
else:print('Skune')

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
l = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
queue1 = deque([1])
queue2 = deque([n])
Fennec = [-1] * (n+1)
Fennec[1] = 0
Snuke = [-1] * (n+1)
Snuke[n] = 0 
while queue1 or queue2:
    if queue1:
        x = queue1.popleft()
        for i in l[x]:
            if Fennec[i] == -1:
                Fennec[i] = Fennec[x] + 1
                queue1.append(i)
    if queue2:
        x = queue2.popleft()
        for i in l[x]:
            if Snuke[i] == -1:
                Snuke[i] = Snuke[x] + 1
                queue2.append(i)
x = 0
y = 0
for i in range(1,n):
    if Fennec[i] >= Snuke[i]:
        x += 1
    else:
        y += 1
if x > y:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
l = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
d = [-1] * (n+1)
d[1],d[n] = 'B','W'
queue1 = deque([1])
queue2 = deque([n])
Fennec = 0
Snuke = 0
while queue1 or queue2:
    if queue1:
        x = queue1.popleft()
        for i in l[x]:
            if d[i] == -1:
                d[i] = 'B'
                Fennec += 1
                queue1.append(i)
    if queue2:
        x = queue2.popleft()
        for i in l[x]:
            if d[i] == -1:
                d[i] = 'W'
                Snuke += 1
                queue2.append(i)
if Fennec > Snuke:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

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


def bfs(v):
    seen = [0]*(N+1)
    queue = deque()
    dist = [-1]*(N+1)
    dist[v] = 0
    seen[v] = 1
    queue.append(v)
    while queue:
        q = queue.popleft()
        for nx in G[q]:
            if seen[nx]:
                continue
            dist[nx] = dist[q] + 1
            seen[nx] = 1
            queue.append(nx)
        # if not G[q]:
        #     queue.popleft()
        #     continue
        # g = G[q].popleft()
        # if seen[g]:
        #     continue
        # seen[g] = 1
        # dist[g] = dist[q] + 1
        # queue.append(g)
    return dist

d_1 = bfs(1)
d_N = bfs(N)
f = 0
s = 0
for v in range(1, N+1):
    if d_1[v] <= d_N[v]:
        f += 1
    else:
        s += 1
if f >= s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import heapq as hq
from collections import deque
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edges[a].append((b,1))
    edges[b].append((a,1))
INF = float("inf")
d = [INF]*N
d[0] = 0
prev = [None]*N
q = [(0,0)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, w in edges[i]:
        if d[j] > d[i]+w:
            d[j] = d[i]+w
            prev[j] = i
            hq.heappush(q, (d[j], j))
path = deque()
i = N-1
while prev[i] != 0:
    path.append(prev[i])
    i = prev[i]
fncq = deque([0])
snkq = deque([N-1])
fnc = 1
snk = 1
visited = [False]*N
visited[0] = True
visited[N-1] = True
while path:
    v = path.popleft()
    fncq.append(v)
    visited[v] = True
    fnc += 1
    if path:
        v = path.pop()
        snkq.append(v)
        visited[v] = True
        snk += 1
po = [fncq, snkq]
while fncq or snkq:
    for i in range(2):
        q = po[i]
        if q:
            v = q.popleft()
            for w,_ in edges[v]:
                if not visited[w]:
                    visited[w] = True
                    q.append(w)
                    if i == 0:
                        fnc += 1
                    else:
                        snk += 1
print("Fennec" if fnc > snk else "Snuke")

Submission status: Wrong Answer

Solution code:
import heapq as hq
from collections import deque
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edges[a].append((b,1))
    edges[b].append((a,1))
INF = float("inf")
d = [INF]*N
d[0] = 0
prev = [None]*N
q = [(0,0)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, w in edges[i]:
        if d[j] > d[i]+w:
            d[j] = d[i]+w
            prev[j] = i
            hq.heappush(q, (d[j], j))
path = deque()
i = N-1
while prev[i] != 0:
    path.append(prev[i])
    i = prev[i]
fncq = deque([0])
snkq = deque([N-1])
fnc = 1
snk = 1
visited = [False]*N
visited[0] = True
visited[N-1] = True
while path:
    fncq.append(path.popleft())
    fnc += 1
    if path:
        snkq.append(path.pop())
        snk += 1
po = [fncq, snkq]
while fncq or snkq:
    for i in range(2):
        q = po[i]
        if q:
            v = q.popleft()
            visited[v] = True
            for w,_ in edges[v]:
                if not visited[w]:
                    visited[w] = True
                    q.append(w)
                    if i == 0:
                        fnc += 1
                    else:
                        snk += 1
print("Fennec" if fnc > snk else "Snuke")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
import heapq as hq
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edges[a].append((b,1))
    edges[b].append((a,1))
INF = float("inf")
d = [INF]*N
d[0] = 0
q = [(0,0)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, w in edges[i]:
        if d[j] > d[i]+w:
            d[j] = d[i]+w
            hq.heappush(q, (d[j], j))
def cnt(n,m):
    ret = 1
    for v,_ in edges[n]:
        if v != m and not visited[v]:
            visited[v] = True
            ret += cnt(v,m)
    return ret
visited = [False]*N
visited[0] = True
fnc = cnt(0,N-1)
visited = [False]*N
visited[N-1] = True
snk = cnt(N-1,0)
if d[N-1] % 2 == 0:
    snk -= 1
print("Fennec" if snk < fnc else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    ad_ls[a-1].append(b-1)
    ad_ls[b-1].append(a-1)
# 最終的にsnukeがnの半分以上のマスを所有していればsnukeの勝ち

# まず、fennecからsnukeへのパスを求める
node_from = [-1] * n
time = [float('inf')] * n
q = deque()

q.append(0)
time[0] = 0

while q:
    now = q.popleft()
    for nex in ad_ls[now]:
        if time[nex] == float('inf'):
            time[nex] = time[now] + 1
            q.append(nex)
            node_from[nex] = now

# ここ
n_snuke_nodes = -(-time[-1]//2)
snuke_list = [0] * n_snuke_nodes
now = n-1
for i in range(n_snuke_nodes):
    snuke_list[i] = now
    now = node_from[now]
NG = now

done = [0] * n
done[NG] = 1
for i in range(n_snuke_nodes):
    done[snuke_list[i]] = 1

# sunke_list内に既にあるノードと、node_fromの最後のすぬけの後のやつには遷移しない
def dfs(now):
    num = 1
    for nex in ad_ls[now]:
        if not done[nex]:
            done[nex] = 1
            num += dfs(nex)
    return num

snuke = 0
for node in snuke_list:
    snuke += dfs(node)
if snuke >= n//2:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    ad_ls[a-1].append(b-1)
    ad_ls[b-1].append(a-1)
# 最終的にsnukeがnの半分以上のマスを所有していればsnukeの勝ち

# まず、fennecからsnukeへのパスを求める
node_from = [-1] * n
time = [float('inf')] * n
q = deque()

q.append(0)
time[0] = 0

while q:
    now = q.popleft()
    for nex in ad_ls[now]:
        if time[nex] == float('inf'):
            time[nex] = time[now] + 1
            q.append(nex)
            node_from[nex] = now

n_snuke_nodes = time[n-1]//2
snuke_list = [0] * n_snuke_nodes
now = n-1
for i in range(n_snuke_nodes):
    snuke_list[i] = now
    now = node_from[now]
NG = node_from[now]

done = [0] * n
done[NG] = 1
for i in range(n_snuke_nodes):
    done[snuke_list[i]] = 1

# sunke_list内に既にあるノードと、node_fromの最後のすぬけの後のやつには遷移しない
def dfs(now):
    num = 1
    for nex in ad_ls[now]:
        if not done[nex]:
            done[nex] = 1
            num += dfs(nex)
    return num

snuke = 0
for node in snuke_list:
    snuke += dfs(node)
if snuke >= n//2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

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

adj = [[]for i in range(N+1)]
for i in range(N-1):
    a,b = ab[i]
    adj[a].append(b)
    adj[b].append(a)


from collections import deque 
#スタック
s = deque([])

cost = [10**10]*(N+1)

s.append([1,0])
while len(s)>0:
    place,time = s.pop()
    if time > cost[place]:
        continue
    cost[place]=time
    for i in adj[place]:
        if time < cost[i]:
            s.append([i,time+1])

#たどる
root = [N]
nowp = N
nowt = cost[N]
while nowt>0:
    for i in adj[nowp]:
        if cost[i]==nowt-1:
            root.append(i)
            nowp=i
            nowt=nowt-1
            break

feneaba = len(root)//2-1
l,r = min(root[feneaba],root[feneaba+1]),max(root[feneaba],root[feneaba+1])

#Union Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

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

#初期化
#根なら-size,子なら親の頂点
par = [-1]*(N+1)

for i in range(N-1):
    a,b = ab[i]
    a,b = min(a,b),max(a,b)
    if a==l and b==r:
        continue
    unite(a,b)

print("Fennec" if size(1)>size(N) else "Sunuke")

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
flag = [False for i in range(n + 1)]
flag2 = [False for i in range(n + 1)]
count_f = 0
count_s = 0
queue = collections.deque([1])
while queue:
    test = queue.popleft()
    flag[test] = True
    for i in graph[test]:
        if flag[i] == False and i != n:
            queue.append(i)
            count_f += 1
queue2 = collections.deque([n])
while queue2:
    test = queue2.popleft()
    flag2[test] = True
    for i in graph[test]:
        if flag2[i] == False and i != 1:
            queue.append(i)
            count_s += 1
common = count_f + count_s - (n - 2)
if common % 2 == 0:
    if count_f >= count_s + 1:
        print("Fennec")
    else:
        print("Snuke")
else:
    if count_f >= count_s:
        print("Fennec")
    else:
        print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
fennec = [10**5 + 10] * n
fennec[0] = 0
snuke = [10**5 + 10] * n
snuke[n - 1] = 0


def bfs(arr, q):
    while len(q) > 0:
        qq = q.popleft()
        for nex in graph[qq[0]]:
            if arr[nex] > qq[1] + 1:
                arr[nex] = qq[1] + 1
                q.append([nex, arr[nex]])


sq, gq = deque(), deque()
sq.append([0, 0])
gq.append([n - 1, 0])
bfs(fennec, sq)
bfs(snuke, gq)
ans = 0
for i in range(n):
    if fennec[i] <= snuke[i]:
        ans += 1
    else:
        ans -= 1

print("Fennec" if ans >= 0 else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
fennec = [10**5 + 10] * n
fennec[0] = 0
snuke = [10**5 + 10] * n
snuke[n - 1] = 0


def bfs(arr, q):
    while len(q) > 0:
        nex_q = []
        for qq in q:
            for nex in graph[qq[0]]:
                if arr[nex] > qq[1] + 1:
                    arr[nex] = qq[1] + 1
                    nex_q.append([nex, arr[nex]])
        q = nex_q[:]


sq, gq = deque(), deque()
sq.append([0, 0])
gq.append([n - 1, 0])
bfs(fennec, sq)
bfs(snuke, gq)
ans = 0
for i in range(n):
    if fennec[i] <= snuke[i]:
        ans += 1
    else:
        ans -= 1

print("Fennec" if ans >= 0 else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(x):
    INF = 10**9
    q = deque()
    q.append(x)
    d = [INF] * n
    d[x] = 0
    while q:
        f = q.pop()
        now = d[f]
        for ce in e[f]:
            if d[ce] == INF:
                d[ce] = now + 1
                q.append(ce)
    return d    


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

    
d0 = dfs(0)
dn = dfs(n-1)
f = 0
for i in range(n):
    if d0[i] <= dn[i]:
        f += 1
s = n - f
print('Fennec') if f > s else print('Snuke')
print(d0, dn, f, s)

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(x):
    INF = 10**9
    q = deque()
    q.append(x)
    d = [INF] * n
    d[x] = 0
    while q:
        f = q.pop()
        now = d[f]
        for ce in e[f]:
            if d[ce] == INF:
                d[ce] = now + 1
                q.append(ce)
    return d    


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

    
d0 = dfs(0)
dn = dfs(n-1)
f = 0
for i in range(n):
    if d0[i] <= dn[i]:
        f += 1
s = n - f
print('Fennec') if f >= s else print('Snuke')

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [[b,1]]
  graph[b] += [[a,1]]

def dijkstra(s):
  # numは最短経路の数
  dist = [float('inf')]*N
  dist[s] = 0
  num = [0]*N
  num[s] = 1
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num

d1, _ = dijkstra(0)
d2, _ = dijkstra(N-1)

a1 = 0
a2 = 0
for i in range(N):
  if d1[i] <= d2[i]:
    a1 += 1
  else:
    a2 += 1

if a1 < a2:
  print('Snuke')
else:
  print('Fennec')

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n = ni()
    e = [[] for _ in range(n)]

    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    dist_f = [-1 for _ in range(n)]
    dist_s = [-1 for _ in range(n)]
    dist_f[0] = 0
    dist_s[n - 1] = 0

    def bfs(que, dist):
        while que:
            q = que.popleft()
            for ei in e[q]:
                if dist[ei] == -1:
                    dist[ei] = dist[q] + 1
                    que.append(ei)
        return dist

    dist_f = bfs(collections.deque([0]), dist_f)
    dist_s = bfs(collections.deque([n - 1]), dist_s)

    f = 0
    s = 0
    for df, ds in zip(dist_f, dist_s):
        if df <= ds:
            f += 1
        else:
            s += 1

    print("Fennec" if f > s else "Sunuke")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import collections
n = int(raw_input())

adj = collections.defaultdict(list)
for _ in range(n-1):
	u,v = map(int, raw_input().split())
	adj[u].append(v)
	adj[v].append(u)
q = collections.deque([(1,0)])
parent = {}
distance = {}

vis = set([1])
while(q):
	u,d = q.popleft()
	distance[u] = d
	for v in adj[u]:
		if v not in vis:
			vis.add(v)
			q.append((v,d+1))
			parent[v] = u

r =  (distance[n] - 1)/2
cur =  n
while(r > 0):
	r -= 1
	cur = parent[cur]

vis = set([cur])
def f(u , adj, parent, vis):
	for v in adj[u]:
		if v not in vis and v != parent[u]:

			vis.add(v)
			f(v, adj, parent , vis)
f(n, adj, parent, vis)
print 'Fennec' if (n - len(vis)  > len(vis)) else 'Snuke'

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n=II()
	G=[[] for _ in range(n+1)]

	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)


	B=[-1]*(n+1)
	W=[-1]*(n+1)
	B[1]=0
	W[n]=0

	Q=deque([1])
	while Q:
		now=Q.popleft()
		for i in G[now]:
			if B[i]==-1:
				B[i]=B[now]+1
				Q.append(i)
	#print(B)

	Q=deque([n])
	while Q:
		now=Q.popleft()
		for i in G[now]:
			if W[i]==-1:
				W[i]=W[now]+1
				Q.append(i)
	#print(W)

	s=0
	f=0
	for i,j in zip(B[1:],W[1:]):
		if i<=j:
			f+=1
		else:
			s+=1
	#print(f,s)

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






if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n=II()
	G=[[] for _ in range(n+1)]

	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)


	B=[-1]*(n+1)
	W=[-1]*(n+1)
	B[1]=0
	W[n]=0

	Q=deque([1])
	while Q:
		now=Q.popleft()
		for i in G[now]:
			if B[i]==-1:
				B[i]=B[now]+1
				Q.append(i)
	#print(B)

	Q=deque([n])
	while Q:
		now=Q.popleft()
		for i in G[now]:
			if W[i]==-1:
				W[i]=W[now]+1
				Q.append(i)
	#print(W)

	a=0
	for i,j in zip(B,W):
		if i>j:
			a+=1
		elif i<j:
			a-=1

	print("Fennec" if a<=0 else "Snuke")






if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n=II()
	G=[[] for _ in range(n+1)]

	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)


	B=[-1]*(n+1)
	W=[-1]*(n+1)
	B[1]=0
	W[n]=0

	Q=deque([1])
	while Q:
		now=Q.popleft()
		for i in G[now]:
			if B[i]==-1:
				B[i]=B[now]+1
				Q.append(i)
	#print(B)

	Q=deque([n])
	while Q:
		now=Q.popleft()
		for i in G[now]:
			if W[i]==-1:
				W[i]=W[now]+1
				Q.append(i)
	#print(W)

	a=0
	for i,j in zip(B,W):
		if i>j:
			a+=1
		elif i<j:
			a-=1

	print("Fennec" if a<0 else "Snuke")






if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from collections import deque
n = int(input())
mp2 = []
route = [[] for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x:int(x)-1,input().split())
    mp2.append((a,b,1))
    mp2.append((b,a,1))
    route[a].append(b)
    route[b].append(a)
inf=float('inf')
d=[inf for i in range(n)]
d[0]=0
prev=[None]*n
p=dict()
for i,j,k in mp2: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[0],0))
while q:
    du, u = heappop(q)
    if d[u]<du: continue
    for v,weight in p.get(u,[]):
        alt=du+weight
        if d[v]>alt:
            d[v]=alt
            prev[v]=u
            heappush(q, (alt,v))

p=[n-1]
while prev[p[-1]]!=None: p.append(prev[p[-1]])
p = p[::-1]
t = p[-(-len(p)//2)-1]

d = deque()
d.append(n-1)
visit = [False for i in range(n)]
siro = 1
while d:
    now = d.popleft()
    for i in route[now]:
        if not visit[i] and i != t:
            visit[i] = True
            d.append(i)
            siro += 1
kuro = n - siro
if kuro <= siro:
    print("Snuke")
elif kuro > siro:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
route = [[] for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x:int(x)-1,input().split())
    route[a].append(b)
    route[b].append(a)
d = deque()
d.append([0,[0]])
visit = [False for i in range(n)]
visit[0] = True
while d:
    if visit[n-1]:
        break
    now = d.popleft()
    for i in route[now[0]]:
        if not visit[i]:
            visit[i] = True
            d.append([i,now[1] + [i]])
            if i == n-1:
                p = now[1] + [i]
                break
t = p[-(-len(p)//2)-1]

d = deque()
d.append(n-1)
visit = [False for i in range(n)]
siro = 1
while d:
    now = d.popleft()
    for i in route[now]:
        if not visit[i] and i != t:
            visit[i] = True
            d.append(i)
            siro += 1
kuro = n - siro
if kuro <= siro:
    print("Snuke")
elif kuro > siro:
    print("Fennec")

Submission status: Wrong Answer

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

masu = [0 for i in range(n)]

kuro = deque()
kuro.append(0)
masu[0] = 1
siro = deque()
siro.append(n-1)
masu[n-1] = -1
while kuro or siro:
    if kuro:
        nowkuro = kuro.popleft()
        for i in route[nowkuro]:
            if masu[i] == 0:
                masu[i] = 1
                kuro.append(i)
    if siro:
        nowsiro = siro.popleft()
        for i in route[nowsiro]:
            if masu[i] == 0:
                masu[i] = -1
                siro.append(i)
t = sum(masu)
if t > 0:
    print("Fennec")
elif t <= 0:
    print("Snuke")