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
N = int(input())
sys.setrecursionlimit(1<<30)
def dfs(x, dis):
    for y in Tree[x]:
        if parent[y] != x:
            parent[x] = y
            dis[y] = dis[x] + 1
            dfs(y, dis)
u,v =1, N
Tree = [[] for _ in range(N+1)]
for i in range(N-1):
    A, B = map(int,input().split())
    Tree[A].append(B)
    Tree[B].append(A)
disT = [-1]*(N+1)
disA= [-1]*(N+1)
disT[u] = 0
disA[v] = 0
parent = [-1]*(N+1)
dfs(u, disT)
parent = [-1]*(N+1)
dfs(v, disA)
if not sum(disT) >= sum(disA):
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque


def bfs(s, flag):
    if flag:
        global check
    else:
        check = [-1] * (n + 1)
    cnt = 0
    q = deque([s, cnt])
    ans = 0
    while q:
        now = q.popleft()
        cnt = q.popleft()
        check[now] = cnt
        ans += 1
        for next in graph[now]:
            if flag:
                if check[next] > cnt + 1:
                    q.append(next)
                    q.append(cnt + 1)
            else:
                if check[next] == -1:
                    q.append(next)
                    q.append(cnt + 1)
    if flag:
        return ans
    else:
        return check


n = int(readline())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
check = bfs(1, False)
print('Snuke' if bfs(n, True) > n / 2 else 'Fennec')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque


def bfs(s, flag):
    if flag:
        global check
    else:
        check = [-1] * (n + 1)
    cnt = 0
    q = deque([s, cnt])
    ans = 0
    while q:
        now = q.popleft()
        cnt = q.popleft()
        check[now] = cnt
        ans += 1
        for next in graph[now]:
            if flag:
                if check[next] > cnt + 1:
                    q.append(next)
                    q.append(cnt + 1)
            else:
                if check[next] == -1:
                    q.append(next)
                    q.append(cnt + 1)
    if flag:
        return ans
    else:
        return check


n = int(readline())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
check = bfs(1, False)
print('Sunuke' if bfs(n, True) > n / 2 else 'Fennec')

Submission status: Wrong Answer

Solution code:
n=int(input())
tree=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)
def dist(k):
  l=[-1]*n
  node=[k]
  while node:
    s=node.pop()
    d=l[s]
    for t in tree[s]:
      if l[t]!=-1:
        continue
      l[t]=d+1
      node.append(t)
  return l
from_fennec=dist(0)
from_snuke=dist(n-1)
res=0
for i,j in zip(from_fennec,from_snuke):
  if i>=j:
    res+=1
  else:
    res-=1
print('Snuke' if res>=0 else 'Fennec')

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
root = 1
stack = [root]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
visited[0] = -1
visited[n] = -1
visited[root] = 1
while stack:
  x = stack.pop()
  for y in graph[x]:
    if visited[y] == 0:
      stack.append(y)
      visited[y] = visited[x]+1
for y in graph[n]:
  if visited[y] != 0:
    dist = visited[y]-1
snk = visited.count(0)+dist//2
fen = n-snk-2
if fen > snk:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
G = [set() for _ in range(N+1)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)

path = []
stack = [1]
vs = set()
while stack:
    v = stack.pop()
    if v > 0:
        vs.add(v)
        path.append(v)
        for u in G[v]:
            if u in vs:
                continue
            if u == N:
                stack = []
                path.append(u)
                break
            stack += [-v, u]
    else:
        path.pop()

x = path[-(-len(path)//2)]
path = []
stack = [1]
vs = set()
while stack:
    v = stack.pop()
    if v > 0:
        vs.add(v)
        for u in G[v]:
            if u in vs:
                continue
            if u == x:
                continue
            stack += [-v, u]
x = len(vs)-2
y = N - 2 - x
if x>y:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
G = [set() for _ in range(N+1)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)

path = []
stack = [1]
vs = set()
while stack:
    v = stack.pop()
    vs.add(v)
    path.append(v)
    if v > 0:
        for u in G[v]:
            if u in vs:
                continue
            if u == N:
                stack = []
                path.append(u)
                break
            stack += [-v, u]
    else:
        path.pop()

x = path[-(-len(path)//2)]
path = []
stack = [1]
vs = set()
while stack:
    v = stack.pop()
    vs.add(v)
    if v > 0:
        for u in G[v]:
            if u in vs:
                continue
            if u == x:
                continue
            stack += [-v, u]
x = len(vs)-2
y = N - 2 - x
if x>y:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
G = [set() for _ in range(N+1)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)

path = []
stack = [1]
vs = set()
while stack:
    v = stack.pop()
    vs.add(v)
    path.append(v)
    if v > 0:
        for u in G[v]:
            if u in vs:
                continue
            if u == N:
                stack = []
                path.append(u)
                break
            stack += [-v, u]
    else:
        path.pop()

x = path[-(-len(path)//2)]
path = []
stack = [1]
vs = set()
while stack:
    v = stack.pop()
    vs.add(v)
    if v > 0:
        for u in G[v]:
            if u in vs:
                continue
            if u == x:
                continue
            stack += [-v, u]
x = len(vs)-2
y = N - 2 - x
if x>=y:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([[0,[0]]])
v=[0]*n
v[0]=1
f=0
while q:
    p=q.popleft()
    #if p[1][-1]==n-1:
        #break
    v[p[0]]=1
    for i in g[p[0]]:
        if v[i]==0:
            v[i]=1
            #print(i)
            if i==n-1:
                r=p[1]+[i]
                f=1
                break
            q.append([i,p[1]+[i]])
    if f==1:
        break
fe=deque(r[:(-(-len(r)//2))])
v=[0]*n
v[r[(-(-len(r)//2))]]=1
for i in fe:
    v[i]=1
exit()
while fe:
    s=fe.popleft()
    for i in g[s]:
        if v[i]==0:
            fe.append(i)
            v[i]=1
x=sum(v)-1
y=n-x
if x>y:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([[0,[0]]])
v=[0]*n
v[0]=1
f=0
while q:
    p=q.popleft()
    #if p[1][-1]==n-1:
        #break
    v[p[0]]=1
    for i in g[p[0]]:
        if v[i]==0:
            v[i]=1
            #print(i)
            if i==n-1:
                r=p[1]+[i]
                f=1
                break
            q.append([i,p[1]+[i]])
    if f==1:
        break
fe=deque(r[:(-(-len(r)//2))])
v=[0]*n
v[(-(-len(r)//2))]=1
v[0]=1
while fe:
    s=fe.popleft()
    for i in g[s]:
        if v[i]==0:
            fe.append(i)
            v[i]=1
x=sum(v)-1
y=n-x
if x>y:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=[[0,[0]]]
v=[0]*n
v[0]=1
f=0
while q:
    p=q.pop(0)
    #if p[1][-1]==n-1:
        #break
    v[p[0]]=1
    for i in g[p[0]]:
        if v[i]==0:
            v[i]=1
            #print(i)
            if i==n-1:
                r=p[1]+[i]
                f=1
                break
            q.append([i,p[1]+[i]])
    if f==1:
        break
fe=r[:(-(-len(r)//2))]
v=[0]*n
v[(-(-len(r)//2))]=1
v[0]=1
while fe:
    s=fe.pop(0)
    for i in g[s]:
        if v[i]==0:
            fe.append(i)
            v[i]=1
x=sum(v)-1
y=n-x
if x>y:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
tree = [[] for i in range(N+1)]

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

dist_fennec = [100001] * (N+1)
dist_snuke = [100001] * (N+1)
q = [1]
dist_fennec[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist_fennec[next] == 100001:
            dist_fennec[next] = dist_fennec[now] + 1
            q.append(next)

q = [N]
dist_snuke[N] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist_snuke[next] == 100001:
            dist_snuke[next] = dist_snuke[now] + 1
            q.append(next)

fennec, snuke = 0, 0
for i in range(1, N+1):
    if dist_snuke[i] <= dist_fennec[i]:
        fennec += 1
    else:
        snuke += 1

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
tree = [[] for i in range(N+1)]

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

dist = [100001] * (N+1)

q = [1]
dist[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist[next] == 100001:
            dist[next] = dist[now] + 1
            q.append(next)

fennec = dist[N]+1
snuke = dist[N]+1
visit = [False] * (N+1)
q = [1]
visit[1] = True
while q:
    now = q.pop()
    for next in tree[now]:
        if not visit[next] and next != N:
            visit[next] = True
            q.append(next)
fennec += sum(visit)

visit = [False] * (N+1)
q = [N]
visit[N] = True
while q:
    now = q.pop()
    for next in tree[now]:
        if not visit[next] and next != 1:
            visit[next] = True
            q.append(next)

snuke += sum(visit)

fennec += (dist[N])//2
snuke += (dist[N]-1)//2




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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
tree = [[] for i in range(N+1)]

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

dist = [100001] * (N+1)

q = [1]
dist[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist[next] == 100001:
            dist[next] = dist[now] + 1
            q.append(next)

fennec = -(dist[N]-1)//2
snuke = -(dist[N])//2
visit = [False] * (N+1)
q = [1]
visit[1] = True
while q:
    now = q.pop()
    for next in tree[now]:
        if not visit[next] and next != N:
            visit[next] = True
            q.append(next)
fennec += sum(visit)

visit = [False] * (N+1)
q = [N]
visit[N] = True
while q:
    now = q.pop()
    for next in tree[now]:
        if not visit[next] and next != 1:
            visit[next] = True
            q.append(next)

snuke += sum(visit)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
tree = [[] for i in range(N+1)]

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

dist = [100001] * (N+1)

q = [1]
dist[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist[next] == 100001:
            dist[next] = dist[now] + 1
            q.append(next)

fennec = -dist[N]//2
snuke = -(dist[N]+1)//2
visit = [False] * (N+1)
q = [1]
visit[1] = True
while q:
    now = q.pop()
    for next in tree[now]:
        if not visit[next] and next != N:
            visit[next] = True
            q.append(next)
fennec += sum(visit)

visit = [False] * (N+1)
q = [N]
visit[N] = True
while q:
    now = q.pop()
    for next in tree[now]:
        if not visit[next] and next != 1:
            visit[next] = True
            q.append(next)

snuke += sum(visit)

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

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10000000)

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

    # path
    goal = N-1
    path = [0]
    candidates = [adj[0]]
    while path[-1] != goal:
        while not candidates[-1]:
            candidates.pop()
            path.pop()
        u = candidates[-1].pop()
        candidates.append([n for n in adj[u] if n != path[-1]])
        path.append(u)


    black = path[(len(path)-1)//2]
    white = path[(len(path)-1)//2+1]

    # count
    path = [black]
    candidates = [[n for n in adj[black] if n != white]]
    cnt = 0
    try:
        while True:
            while not candidates[-1]:
                cnt += 1
                candidates.pop()
                path.pop()
            u = candidates[-1].pop()
            candidates.append([n for n in adj[u] if n != path[-1]])
            path.append(u)
    except IndexError:
        pass
    bscore = cnt
    print('Fennec' if bscore*2 > N else 'Snuke')

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10000000)

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

    # path
    goal = N-1
    path = [0]
    candidates = [adj[0]]
    while path[-1] != goal:
        if not candidates[-1]:
            candidates.pop()
            path.pop()
        else:
            u = candidates[-1].pop()
            candidates.append([n for n in adj[u] if n != path[-1]])
            path.append(u)



    black = path[(len(path)-1)//2]
    white = path[(len(path)-1)//2+1]

    # count
    def rec(prev, cur):
        return sum(rec(cur, n) for n in adj[cur] if n != prev) + 1

    bscore = rec(white,black)
    print('Fennec' if bscore*2 > N else 'Snuke')

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not x==y: # 根が同じでない場合のみ併合する
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] # 要素数を併合
                self.par[x] = y # 根を付け替えている
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
        
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y) 

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    from collections import defaultdict,deque
    G = defaultdict(list)
    D = []
    for i in range(N-1):
        a, b = map(int,input().split())
        D.append([a,b])
        G[a].append(b)
        G[b].append(a)
    
    que = deque()
    que.append(1)
    visited = {}
    oya = [-1]*(10**5+1)
    while que != deque():
        v = que.pop()
        visited[v] = 1
        if v == N:
            break
        else:
            for i in G[v]:
                if not i in visited:
                    oya[i] = v
                    que.append(i)
    now = N
    path = []
    while now != -1:
        path.append(now)
        now = oya[now]
    path = path[::-1]
    print(path)
    L = len(path)
    if L%2==0:
        d1,d2 = path[L//2-1],path[L//2]
    else:
        d1,d2 = path[L//2],path[L//2+1]
    G2 = UnionFind(N)
    
    for i in D:
        a,b = i
        if not {a,b} == {d1,d2}:
            G2.union(a,b)
    one = -G2.par[G2.find(1)]
    enu = -G2.par[G2.find(N)]
    
    if one>enu:
        print("Fennec")
    else:
        print("Snuke")
    

main()

Submission status: Wrong Answer

Solution code:
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)
#print(data)

data_path = 0
data_f = 0
data_s = 0

stack = [0]
used = [True for i in range(n)]
while len(stack) > 0:
    now = stack.pop()
    used[now] = False
    for i in data[now]:
        if i != n-1 and used[i]:
            stack.append(i)
            data_f+=1

stack = [n-1]
used = [True for i in range(n)]
while len(stack) > 0:
    now = stack.pop()
    used[now] = False
    for i in data[now]:
        if i != 0 and used[i]:
            stack.append(i)
            data_s+=1

data_path = data_f + data_s - n + 2
data_f -= data_path
data_s -= data_path
#print(data_f,data_s,data_path)
if data_path%2 == 1:
    data_f += 1
if data_f < data_s:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
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)
print(data)

data_path = 0
data_f = 0
data_s = 0

stack = [0]
used = [True for i in range(n)]
while len(stack) > 0:
    now = stack.pop()
    used[now] = False
    for i in data[now]:
        if i != n-1 and used[i]:
            stack.append(i)
            data_f+=1

stack = [n-1]
used = [True for i in range(n)]
while len(stack) > 0:
    now = stack.pop()
    used[now] = False
    for i in data[now]:
        if i != 0 and used[i]:
            stack.append(i)
            data_s+=1

data_path = data_f + data_s - n + 2
data_f -= data_path
data_s -= data_path
#print(data_f,data_s,data_path)
if data_path%2 == 1:
    data_f += 1
if data_f < data_s:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:

#
#フェネックとすぬけさんが最短でお互いのマスへ向かう時の、ぶつかる点を求めて
#木を分割する。分割した二つのマスを数えて比較し、大きい方が勝利

import sys
sys.setrecursionlimit(1000000)

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)

#二人がぶつかる点を求める（木を分割する点を求める）
col = [ -1 for i in range(N)]
col[0] = 0
p = []
path = [ 0 for i in range(10**5+1)]
def dfs(n,c):
    global p
    if n == N - 1:
        p = path
    path[c] = n
    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            dfs(v,c+1)
            if p:
                return
dfs(0,0)

t = col[N-1] + 1
if t % 2 ==0:
    sn = p[t//2]
else:
    sn = p[t//2+1]


#フェネック側の木のマス数を数える
colfn = [ -1 for i in range(N)]
colfn[0] = 0
def dfs2(n,c):

    for v in e[n]:
        if v == sn:
            continue
        elif colfn[v] == -1:
            colfn[v] = c + 1
            dfs2(v,c+1)

dfs2(0,0)

fennec = 0
for i in range(N):
    if colfn[i] != -1:
        fennec += 1


#すぬけさん側は全マス数からフェネックのマスを引けば良い
snuke = N - fennec - 1

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

Submission status: Wrong Answer

Solution code:
import sys

p = []
path = [ 0 for i in range(10**5+1)]
def main():

    sys.setrecursionlimit(1000000)

    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)

    col = [ -1 for i in range(N)]
    col[0] = 0
    
    def dfs(n,c):
        global p
        if n == N - 1:
            p = path
        path[c] = n
        for v in e[n]:
            if col[v] == -1:
                col[v] = c + 1
                dfs(v,c+1)
    dfs(0,0)

    t = col[N-1] + 1
    if t % 2 ==0:
        sn = p[t//2]
    else:
        sn = p[t//2+1]


    colfn = [ -1 for i in range(N)]
    colfn[0] = 0
    def dfs2(n,c):

        for v in e[n]:
            if v == sn:
                continue
            elif colfn[v] == -1:
                colfn[v] = c + 1
                dfs2(v,c+1)

    dfs2(0,0)

    fennec = -1
    for i in range(N):
        if colfn[i] != -1:
            fennec += 1

    snuke = N - fennec - 2
    if fennec > snuke:
        print("Fennec")
    else:
        print("Snuke")



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

p = []
def main():

    sys.setrecursionlimit(1000000)

    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)

    col = [ -1 for i in range(N)]
    col[0] = 0
    
    def dfs(n,c,path):
        global p
        #path =  path  + [n]
        path.append(n)
        if n == N - 1:
            p = path
        for v in e[n]:
            if col[v] == -1:
                col[v] = c + 1
                dfs(v,c+1,path)
                if p:
                    return
    dfs(0,0,[])

    if len(p) % 2 ==0:
        sn = p[len(p)//2]
    else:
        sn = p[len(p)//2+1]


    colfn = [ -1 for i in range(N)]
    colfn[0] = 0
    def dfs2(n,c):

        for v in e[n]:
            if v == sn:
                continue
            elif colfn[v] == -1:
                colfn[v] = c + 1
                dfs2(v,c+1)

    dfs2(0,0)

    fennec = -1
    for i in range(N):
        if colfn[i] != -1:
            fennec += 1

    snuke = N - fennec - 2
    if fennec > snuke:
        print("Fennec")
    else:
        print("Snuke")



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

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)

col = [ -1 for i in range(N)]
col[0] = 0
def dfs(n,c):
    if not e[n]:
        return

    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            dfs(v,c+1)

dfs(0,0)

colf = [ -1 for i in range(N)]
colf[0] = 0
def dfsf(n,c):

    if not e[n]:
        return
    for v in e[n]:
        if v == N - 1:
            #colf[v] = c + 1
            continue
        elif colf[v] == -1:
            colf[v] = c + 1
            dfsf(v,c+1)
dfsf(0,0)

cols = [ -1 for i in range(N)]
cols[N-1] = 0
def dfss(n,c):
    
    if not e[n]:
        return

    for v in e[n]:
        if v == 0:
            #cols[v] = c + 1
            continue
        elif cols[v] == -1:
            cols[v] = c + 1
            dfss(v,c+1)
dfss(N-1,0)



fennec,snuke = 0,0

for i in range(N):
    if colf[i] != -1:
        fennec += 1
    if cols[i] != -1:
        snuke += 1

t = col[N-1] - 1
if t % 2 == 0:
    fennec += (t//2)
    snuke += (t//2)
else:
    fennec += (t//2) + 1
    snuke += (t//2)
    
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(graph, start, goal):
    s_stack = deque()
    g_stack = deque()
    visited = [False for i in range(N+1)]
    s_stack.append(start)
    g_stack.append(goal)
    visited[start] = True
    visited[goal] = True
    s_cnt = 1
    g_cnt = 1
    while s_stack or g_stack:
        if s_stack:
            a = s_stack.popleft()
            for b in graph[a].keys():
                if not visited[b]:
                    s_stack.append(b)
                    visited[b] = True
                    s_cnt += 1
        if g_stack:
            a = g_stack.popleft()
            for b in graph[a].keys():
                if not visited[b]:
                    g_stack.append(b)
                    visited[b] = True
                    g_cnt += 1
    return s_cnt > g_cnt

N = int(input())
graph = {}
for i in range(N-1):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
print('Fennec' if dfs(graph,1,N) else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(graph: list, start: int):
    n = len(graph)
    dist = [-1]*n

    que = deque([(start, 0)])

    while que:
        cur_node, cur_dist = que.popleft()
        dist[cur_node] = cur_dist

        for nex in graph[cur_node]:
            if dist[nex] < 0:
                dist[nex] = cur_dist + 1
                que.append((nex, cur_dist+1))

    return dist

n = ni()

graph = [[] for _ in range(n)]
for _ in range(n-1):
    x, y = li_()
    graph[x].append(y)
    graph[y].append(x)

fenec = bfs(graph, 0)
snuke = bfs(graph, n-1)

fenec_saki = 0
for d1, d2 in zip(fenec, snuke):
    if d1 < d2:
        fenec_saki += 1
    elif d1 > d2:
        fenec_saki -= 1

if fenec_saki == 0:
    if n%2:
        print("Fennec")
    else:
        print("Snuke")

elif fenec_saki > 0:
    print("Fennec")

else:
    print("Snuke")

Submission status: Wrong Answer

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

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
prev_list = [-1 for i in range(N)]
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            prev_list[v1]=v
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える

path = [N-1]
v=N-1
while prev_list[v]!=-1:
    path.append(prev_list[v])
    v=prev_list[v]

a=path[min_path_list[N-1]//2]
b=path[min_path_list[N-1]//2+1]
for i in range(len(e_list[a])):
    if e_list[a][i]==b:
        break
del e_list[a][i]

for i in range(len(e_list[b])):
    if e_list[b][i]==a:
        break
del e_list[b][i]

vi = 0 #時と場合によってここを変える

Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
count = 1
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            count+=1

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

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())

#neighbor
#0~N-1でアクセス
ngb = [[] for _ in range(N)]

#入力
#すべて-1ベースに
for _ in range(N-1):
  a,b = mi()
  a -= 1
  b -= 1
  ngb[a].append(b)
  ngb[b].append(a)

start = 0
goal = N-1

#nodes[番号][0]には探索済みならstartからの距離、未探索なら-1を格納
#nodes[番号][1]には（探索済みなら）「何番のノードから来たか(0~N-1)」を格納
nodes = [[-1, -1] for _ in range(N)]

#nodesにスタート地点を入れ、stackを初期化
nodes[start][0] = 0
nodes[start][1] = -1
stack = []
for eachngb in ngb[start]:
  stack.append(eachngb)
  nodes[eachngb][0] = 1
  nodes[eachngb][1] = start

#phase1 start->goalの最短距離を探索
while 1:
  try:
    nownode = stack.pop()
  except:
    break

  if nownode == goal:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if nodes[eachngb][0] == -1:
      stack.append(eachngb)
      #距離を+1して入れ、今のノード番号（どこから来たか、となる）を入れる
      nodes[eachngb][0] = nodes[nownode][0]+1
      nodes[eachngb][1] = nownode

#phase2 B, Wの根を見つける
length = nodes[goal][0] #スタートからゴールへの距離
FenRootPos = length // 2 #Fenの根がある距離
SnRootPos = FenRootPos + 1 #Snukeの根がある距離
FenRoot = -1 #Fenの根ノード番号
SnRoot = -1 #Snukeの根ノード番号

#ゴールからフェネックの根がある場所まで、順に逆走していく
nextnode = goal
#このループ内において、iは今見ているノードのスタートからの距離を表す
for i in range(length, FenRootPos-1, -1):
  nownode = nextnode
  if i == SnRootPos:
    SnRoot = nownode
  elif i == FenRootPos:
    FenRoot = nownode
  nextnode = nodes[nownode][1]

#phase3 B, Wそれぞれの根から、その木のノード数を数える
#お互いの根は探索済み(0)とすることで、重複を避ける

#まずはFen
#探索済みかどうか
ndsFen = [-1] * N
ndsFen[SnRoot] = 0
ndsFen[FenRoot] = 0
stkFen = []
stkFen.append(FenRoot)
FenCnt = 0
while 1:
  try:
    nownode = stkFen.pop()
  except:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if ndsFen[eachngb] == -1:
      stkFen.append(eachngb)
      #今回は距離は関係無いので、0を入れるだけでいい
      ndsFen[eachngb] = 1
      FenCnt += 1

#次はSnuke
#探索済みかどうか
ndsSn = [-1] * N
ndsSn[FenRoot] = 0
ndsSn[SnRoot] = 0
stkSn = []
stkSn.append(SnRoot)
SnCnt = 0
while 1:
  try:
    nownode = stkSn.pop()
  except:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if ndsSn[eachngb] == -1:
      stkFen.append(eachngb)
      #今回は距離は関係無いので、0を入れるだけでいい
      ndsSn[eachngb] = 1
      SnCnt += 1

print('Fennec' if FenCnt > SnCnt else 'Snuke')