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:
import sys
sys.setrecursionlimit(1000000)

N = int(input())

G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append(b)
    G[b].append(a)


def dfs(v, p, c, distance):  # 現在の頂点v, vの親p, 現在の距離c
    distance[v] = c
    for nv in G[v]:
        if visited[nv] is False:
            if nv == p:
                continue
            dfs(nv, v, c+1, distance)
    return


distance_f = [-1]*(N+1)
visited = [False] * (N+1)
dfs(1, -1, 0, distance_f)

distance_s = [-1]*(N+1)
visited = [False] * (N+1)
dfs(N, -1, 0, distance_s)

# print(distance_f)
# print(distance_s)

c = 0
for i in range(N):
    if distance_f[i] <= distance_s[i]:
        c += 1
    else:
        c -= 1

if c > 0:
    print('Fennec')
elif c < 0:
    print('Snuke')
else:
    if distance_f[N] % 2 == 0:
        print('Snuke')
    else:
        print('Fennec')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())

G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append(b)
    G[b].append(a)


def dfs(v, p, c, distance):  # 現在の頂点v, vの親p, 現在の距離c
    distance[v] = c
    for nv in G[v]:
        if visited[nv] is False:
            if nv == p:
                continue
            dfs(nv, v, c+1, distance)
    return


distance_f = [-1]*(N+1)
visited = [False] * (N+1)
dfs(1, -1, 0, distance_f)

distance_s = [-1]*(N+1)
visited = [False] * (N+1)
dfs(N, -1, 0, distance_s)

# print(distance_f)
# print(distance_s)

c = 0
for i in range(N):
    if distance_f[i] <= distance_s[i]:
        c += 1
    else:
        c -= 1

if c > 0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

def solve(E):
    from collections import deque
    D = [None]*N
    D[0] = 0
    prev = [None]*N
    q = deque()
    q.append(0)
    while q:
        u = q.popleft()
        alt = D[u] + 1
        for v in E[u]:
            if D[v] is None:
                prev[v] = u
                D[v] = alt
                q.append(v)
                if v == N-1:
                    break
    if D[N-1] % 2 == 0:
        Dcenter = D[N-1]//2
        u = N-1
        while D[u] == Dcenter:
            u = prev[u] 
        center = u
        F = count(prev[u], prev=u)
    else:
        Dcenter = (D[N-1]-1)//2
        u = N-1
        while D[u] == Dcenter:
            u = prev[u] 
     
        F = count(prev[u], prev=u)
    S = N-F
    if S == F:
        return "Fennec"
    elif S < F:
        return "Fennec"
    else:
        return "Snuke"


def count(u, prev):
    c = 1
    for k in E[u]:
        if k == prev:
            continue
        c += count(k, u)
    return c
    

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)
#for v in E[0]: print(v+1, count(v, prev=0))
print(solve(E))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

def solve(E):
    from collections import deque
    D = [None]*N
    D[0] = 0
    prev = [None]*N
    q = deque()
    q.append(0)
    while q:
        u = q.popleft()
        alt = D[u] + 1
        for v in E[u]:
            if D[v] is None:
                prev[v] = u
                D[v] = alt
                q.append(v)
                if v == N-1:
                    break
    if D[N-1] % 2 == 0:
        Dcenter = D[N-1]//2
        u = N-1
        while D[u] == Dcenter:
            u = prev[u] 
        center = u
        F = count(prev[u], prev=u)
    else:
        Dcenter = (D[N-1]-1)//2
        u = N-1
        while D[u] == Dcenter:
            u = prev[u] 
     
        F = count(prev[u], prev=u)
    S = N-F
    if S == F:
        return "Snuke"
    elif S < F:
        return "Fennec"
    else:
        return "Snuke"


def count(u, prev):
    c = 1
    for k in E[u]:
        if k == prev:
            continue
        c += count(k, u)
    return c
    

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)
#for v in E[0]: print(v+1, count(v, prev=0))
print(solve(E))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

def solve(E):
    from collections import deque
    D = [None]*N
    D[0] = 0
    prev = [None]*N
    q = deque()
    q.append(0)
    while q:
        u = q.popleft()
        alt = D[u] + 1
        for v in E[u]:
            if D[v] is None:
                prev[v] = u
                D[v] = alt
                q.append(v)
                if v == N-1:
                    break
    if D[N-1] % 2 == 0:
        Dcenter = D[N-1]//2
        u = N-1
        while D[u] == Dcenter:
            u = prev[u] 
        center = u
        F = count(prev[u], prev=u)
    else:
        Dcenter = (D[N-1]-1)//2
        u = N-1
        while D[u] == Dcenter:
            u = prev[u] 
     
        F = count(prev[u], prev=u)
    S = N-F
    if S == F:
        return "Sunuke"
    elif S < F:
        return "Fennec"
    else:
        return "Sunuke"


def count(u, prev):
    c = 1
    for k in E[u]:
        if k == prev:
            continue
        c += count(k, u)
    return c
    

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)
#for v in E[0]: print(v+1, count(v, prev=0))
print(solve(E))

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
visited = [0]*n
visited[0] = 1
visited[n-1] = 1
visited_all = [1]*n
nextF = edge[0]
nextS = edge[n-1]
black = 1
white = 1
while visited != visited_all:
    l = []
    for f in nextF:
        if visited[f] == 0:
            visited[f] = 1
            black += 1
            for x in edge[f]:
                l.append(x)
            nextF = l
    l = []
    for f in nextF:
        if visited[f] == 0:
            visited[f] = 1
            black += 1
            for x in edge[f]:
                l.append(x)
            nextF = l
if black > white:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import*
N,*AB=map(int,open(0).read().split())
E=[[]for _ in range(N+1)]
for a,b in zip(*[iter(AB)]*2):
	E[a]+=[b]
	E[b]+=[a]
def g(s):
	Q=deque([s]);d=[0]*(N+1)
	while Q:
		v=Q.popleft()
		for u in E[v]:
			if d[u]==0:
				Q+=[u]
				d[u]=d[v]+1
	return d[1:]
print("FSennunkeec"[0<sum(1 if f<=s else-1 for f,s in zip(g(1),g(N)))::2])

Submission status: Wrong Answer

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)


def get_dist(src):
    Q = deque([src])
    dist = [0] * (N + 1)
    while Q:
        v =  Q.popleft()
        for u in E[v]:
            if dist[u]:
                Q.append(u)
                dist[u] = dist[v] + 1
    return dist[1:]

F = get_dist(1)
S = get_dist(N)

fennec, snuke = 0, 0
for f, s in zip(F, S):
    if f <= s:
        fennec += 1
    else:
        snuke += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque


N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)


def get_dist(src):
    Q = deque([(src, 0)])
    dist = [-1] * (N + 1)
    while Q:
        v, d = Q.popleft()
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                Q.append((u, d + 1))
    return dist[1:]

F = get_dist(1)
S = get_dist(N)

fennec, snuke = 0, 0
for f, s in zip(F, S):
    if f < s:
        fennec += 1
    else:
        snuke += 1

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

path = [0] * n
def dfs(v):
    if v == n-1:
        return True

    for v_next in edge[v]:
        if path[v_next] == 0:
            path[v_next] = 1
            if dfs(v_next):
                return True
            path[v_next] = 0

    return False
path[0] = 1
dfs(0)
# print(path)

visited = [0] * n
def dfs2(v):
    for v_next in edge[v]:
        if visited[v_next] == 0 and path[v_next] == 0:
            visited[v_next] = 1
            dfs2(v_next)
dfs2(0)
# print(visited)

n_f = (sum(path) + 1) // 2 + sum(visited)
if n_f > n // 2:
    ans = "Fennec"
else:
    ans = "Snuke"

print(ans)

Submission status: Wrong Answer

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

class Node:
    def __init__(self, id):
        self.id = id
        self.link = []
        self.color = 0
        self.check = False

def main():
    N = int(input())

    nodes = [Node(i) for i in range(N+1)]

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

    black = deque()
    black.append((nodes[1], 0))
    nodes[1].check = True
    nodes[N].check = True
    black_count = 1
    while len(black) > 0:
        node, cost = black.popleft()
        for nex in node.link:
            if nex.id == N:# 相手のマス
                wid = cost + 1
            elif not nex.check:
                black.append((nex, cost+1))
                nex.check = True
                black_count += 1
    white_count = N - black_count + wid // 2
    black_count = N - white_count
    if black_count <= white_count:
        print("Snuke")
    else:
        print("Fennec")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import math

N=int(input())

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

depth=[[0]*N for i in range(2)]

def dfs(d, i, p, k=0):
	for t in G[i]:
		if t!=p:
			depth[k][t]=d
			dfs(d+1, t, i,k)


dfs(1,0,-1, 0)
dfs(1,N-1,-1, 1)

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

print('Fennec' if cnt*2>N else 'Snuke')
print(depth[0])
print(depth[1])

Submission status: Wrong Answer

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N = int(input())
board = [ [0 for _ in range(N)] for _ in range(N) ]
painted = [''] * N

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

painted[0] = 'F'
painted[N-1] = 'S'

#print(board)

def get_next_point(pos, char):
    for i in range(N):
        if board[pos][i] == 1:
            if painted[i] == '':
                return i

    return -1


turn = 0
while True:
    if turn == 0:
        char = 'F'
    else:
        char = 'S'

    for i in range(N):
        if painted[i] == char:
            idx = get_next_point(i, char)
            if idx == -1:
                if char == 'F':
                    print('Snuke')
                    exit()
                else:
                    print('Fennec')
                    exit()

            painted[idx] = char
#            print(painted)
            break

    turn ^= 1

Submission status: Wrong Answer

Solution code:

n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]

V = [0] * (n+1)
D = [[0, 0] for i in range(n+1)]
M = [[] for i in range(n+1)]

for i in range(n-1):
    M[A[i][0]].append(A[i][1])
    M[A[i][1]].append(A[i][0])

# print(M)

def d(x, dis, s):
    if V[x] == 0:
        V[x] = 1
        D[x][0] = dis
        D[x][1] = s
        # print(D)
        # print(M[x],s)
        for i in M[x]:
            
            if V[i] == 0:
                if i == n:
                    s = 1
                Q.append([i, dis+1, s])
                # print(Q)


Q = [[1, 0, 0]]
st = 0
while st < len(Q):
    d(Q[st][0], Q[st][1], Q[st][2])
    st += 1


s_sum = 0
for i in range(n+1):
    s_sum += D[i][1]



aida = D[n][0] - 1
f_sum = n - aida - s_sum

# print(aida, s_sum, f_sum)

if aida % 2 == 0:
    if s_sum >= f_sum:
        print("Snuke")
    else:
        print("Fennec")
else:
    if s_sum > f_sum:
        print("Snuke")
    else:
        print("Fennec")

Submission status: Wrong Answer

Solution code:
# ABC067D - Fennec VS. Snuke (ARC078D)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, x: int, y: int) -> None:
    D[y][v] = x
    for u in G[v]:
        if not D[y][u]:
            dfs(u, x + 1, y)


def main():
    global G, D
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    D = [[0] * (N + 1) for _ in range(2)]
    dfs(1, 1, 0), dfs(N, 1, 1)
    b, w = 0, 0
    for i, j in zip(*D):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(600000)

N = int(input())

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

def dfs(p, checked, now):
    #print(p, checked, now)
    if p == N-1:
        return now, True
    ok = False
    for q in graph[p]:
        if not checked[q]:
            now.append(q)
            checked[q] = True
            nbw, ok1 = dfs(q, checked, now)
            if ok1:
                bw = nbw
                ok = True
    if not ok:
        now.pop()
        return now, False
    return bw, True

checked = [False for _ in range(N)]
checked[0] = True
bw, ok = dfs(0, checked, [0])
#print(bw)

between = [False for _ in range(N)]
for b in bw:
    between[b] = True

def dfs2(p, checked, c):
    c += 1
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(0, between, 0)
cN = dfs2(N-1, between, 0)
#print(c0, cN)

if len(bw) % 2 != 0:
    c0 += 1

if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(600000)

N = int(input())

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

def dfs(p, checked, now):
    #print(p, checked, now)
    if p == N-1:
        return now, True
    ok = False
    for q in graph[p]:
        if not checked[q]:
            now.append(q)
            checked[q] = True
            bw, ok1 = dfs(q, checked, now)
            ok = ok1 or ok
    if not ok:
        now.pop()
        return now, False
    return bw, True

checked = [False for _ in range(N)]
checked[0] = True
bw, ok = dfs(0, checked, [0])
#print(bw)

between = [False for _ in range(N)]
for b in bw:
    between[b] = True

def dfs2(p, checked, c):
    c += 1
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(0, between, 0)
cN = dfs2(N-1, between, 0)
#print(c0, cN)

if len(bw) % 2 != 0:
    c0 += 1

if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())

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

def dfs(p, checked, now, bw):
    if p == N-1:
        return now
    update = False
    for q in graph[p]:
        if not checked[q]:
            update = True
            now.append(q)
            checked[q] = True
            bw = dfs(q, checked, now, bw)
    if not update:
        now.pop()
    return bw

checked = [False for _ in range(N)]
checked[0] = True
bw = dfs(0, checked, [0], [])
cb = len(bw) - 2

between = [False for _ in range(N)]
for b in bw:
    between[b] = True

def dfs2(p, checked, c):
    c += 1
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(0, between, 0)-1
cN = dfs2(N-1, between, 0)-1

if cb % 2 == 0:
    c0 += cb//2
    cN += cb//2
else:
    c0 += cb//2+1
    cN += cb//2

if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())

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

def dfs(p, checked, now, bw):
    if p == N-1:
        return now
    update = False
    for q in graph[p]:
        new = now[:]
        if not checked[q]:
            update = True
            new.append(q)
            checked[q] = True
            bw = dfs(q, checked, new, bw)
    if not update:
        now.pop()
    return bw

checked = [False for _ in range(N)]
checked[0] = True
bw = dfs(0, checked, [0], [])
cb = len(bw) - 2

between = [False for _ in range(N)]
for b in bw:
    between[b] = True

def dfs2(p, checked, c):
    c += 1
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(0, between, 0)-1
cN = dfs2(N-1, between, 0)-1

if cb % 2 == 0:
    c0 += cb//2
    cN += cb//2
else:
    c0 += cb//2+1
    cN += cb//2

if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())

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

def dfs(p, checked, now, bw):
    if p == N-1:
        return now
    update = False
    for q in graph[p]:
        new = now[:]
        if not checked[q]:
            update = True
            new.append(q)
            checked[q] = True
            bw = dfs(q, checked, new, bw)
    if not update:
        now.pop()
    return bw

checked = [False for _ in range(N)]
bw = dfs(0, checked, [0], [])
cb = len(bw) - 2

between = [False for _ in range(N)]
for b in bw:
    between[b] = True

def dfs2(p, checked, c):
    c += 1
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(0, between, 0)-1
cN = dfs2(N-1, between, 0)-1

if cb % 2 == 0:
    c0 += cb//2
    cN += cb//2
else:
    c0 += cb//2+1
    cN += cb//2

if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())

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

def dfs(p, checked, now, bw):
    checked[p] = True
    if p == N-1:
        return now
    update = False
    for q in graph[p]:
        new = now[:]
        if not checked[q]:
            update = True
            new.append(q)
            bw = dfs(q, checked, new, bw)
    if not update:
        now.pop()
    return bw

checked = [False for _ in range(N)]
bw = dfs(0, checked, [0], [])
cb = len(bw) - 2

between = [False for _ in range(N)]
for b in bw:
    between[b] = True

def dfs2(p, checked, c):
    checked[p] = True
    c += 1
    for q in graph[p]:
        if not checked[q]:
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(0, between, 0)-1
cN = dfs2(N-1, between, 0)-1

if cb % 2 == 0:
    c0 += cb//2
    cN += cb//2
else:
    c0 += cb//2+1
    cN += cb//2

if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N = int(input())

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

def dfs(p, checked, now, bw):
    checked[p] = True
    if p == N-1:
        return now
    update = False
    for q in graph[p]:
        new = now[:]
        if not checked[q]:
            update = True
            new.append(q)
            bw = dfs(q, checked, new, bw)
    if not update:
        now.pop()
    return bw

checked = [False for _ in range(N)]
bw = dfs(0, checked, [0], [])
cb = len(bw) - 2

between = [False for _ in range(N)]
for b in bw:
    between[b] = True

def dfs2(p, checked, c):
    checked[p] = True
    c += 1
    for q in graph[p]:
        if not checked[q]:
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(0, between, 0)-1
cN = dfs2(N-1, between, 0)-1

if cb % 2 == 0:
    c0 += cb//2
    cN += cb//2
else:
    c0 += cb//2+1
    cN += cb//2

if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

nbr=[[] for _ in range(n)]
for i in range(n-1):
    nbr[l[i][0]-1].append(l[i][1]-1)
    nbr[l[i][1]-1].append(l[i][0]-1)
def sm(i,p):
    s=0
    for x in nbr[i]:
        if x!=p:s+=sm(x,i)
    return s+1
flg=False
f=0
c=[]
def dfs(i,p):
    global flg
    global c
    if i==n-1:flg=True
    if not flg:
        for x in nbr[i]:
            if x!=p:dfs(x,i)
    if flg:
        c.append(i)
dfs(0,-1)
idx=(len(c)+1)//2
print('Fennec' if sm(c[::-1][idx],c[::-1][idx-1])*2<n else 'Snuke')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if not (a % 3 and b % 3 and (a + b) % 3):
        print("Possible")
    else:
        print("Impossible")
    return

#B
def B():
    _, n = LI()
    l = LI()
    l.sort(reverse = True)
    print(sum(l[:n]))
    return

#C
def C():
    n = II()
    a = LI()
    for i in range(n-1):
        a[i + 1] += a[i]
    maxa = a[-1]
    ans = inf
    for i in range(n-1):
        ans = min(ans, abs(2 * a[i] - maxa))
    print(ans)
    return

#D
def D():
    n = II()
    edg = [[] for i in range(n)]
    for _ in range(n - 1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    rank = [0] * n
    q = deque()
    q.append(0)
    rank[0] = 1
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i]:
                continue
            rank[i] = rank[p] + 1
            q.appendleft(i)
    k = 2
    q = deque()
    q.append(n - 1)
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i] < rank[p]:
                if rank[i] <= k:
                    a = p
                    break
                q.appendleft(i)
                k += 1
    ans1 = 1
    ans2 = 1
    check = [True] * n
    q = deque()
    q.append(a)
    check[a] = False
    while q:
        p = q.pop()
        print(p)
        for i in edg[p]:
            if rank[i] > rank[p]:
                q.append(i)
                ans1 += 1
                check[i] = False
    q = deque()
    q.append(0)
    check[0] = False
    while q:
        p = q.pop()
        for i in edg[p]:
            if check[i]:
                q.append(i)
                ans2 += 1
                check[i] = False
    print(["Fennec", "Snuke"][ans1 >= ans2])
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if not (a % 3 and b % 3 and (a + b) % 3):
        print("Possible")
    else:
        print("Impossible")
    return

#B
def B():
    _, n = LI()
    l = LI()
    l.sort(reverse = True)
    print(sum(l[:n]))
    return

#C
def C():
    n = II()
    a = LI()
    for i in range(n-1):
        a[i + 1] += a[i]
    maxa = a[-1]
    ans = inf
    for i in range(n-1):
        ans = min(ans, abs(2 * a[i] - maxa))
    print(ans)
    return

#D
def D():
    n = II()
    edg = [[] for i in range(n)]
    for _ in range(n - 1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    rank = [0] * n
    q = deque()
    q.append(0)
    rank[0] = 1
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i]:
                continue
            rank[i] = rank[p] + 1
            q.appendleft(i)
    k = rank[n - 1] - (rank[n - 1] - 2) // 2
    q = deque()
    q.append(n - 1)
    while q:
        p = q.pop()
        if rank[p] == k:
            a = p
            break
        for i in edg[p]:
            if rank[i] < rank[p]:
                if rank[i] == k:
                    a = i
                    break
                q.append(i)
    ans1 = 1
    ans2 = 1
    check = [True] * n
    q = deque()
    q.append(a)
    check[a] = False
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i] > rank[p]:
                q.append(i)
                ans1 += 1
                check[i] = False
    q = deque()
    q.append(0)
    check[0] = False
    while q:
        p = q.pop()
        for i in edg[p]:
            if check[i]:
                q.append(i)
                ans2 += 1
                check[i] = False
    print(["Fennec", "Snuke"][ans1 <= ans2])
    return

#Solve
if __name__ == '__main__':
    D()