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: Accepted

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 = 1
s = 1
for v in range(2, N):
    if d_1[v] <= d_N[v]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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.pop()
    fncq.append(v)
    visited[v] = True
    fnc += 1
    if path:
        v = path.popleft()
        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: Accepted

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = (int(x)-1 for x in input().split())
  graph[a].append(b)
  graph[b].append(a)

from collections import deque
def bfs(s:int)->list:
  dist = [-1]*n
  dist[s] = 0
  que = deque([s])
  while que:
    u = que.popleft()
    for v in graph[u]:
      if dist[v] != -1: continue
      dist[v] = dist[u] + 1
      que.append(v)
  return dist

dfen = bfs(0)
dsnu = bfs(n-1)
pfen = 0
psnu = 0
for i in range(n):
  if dfen[i] <= dsnu[i]: pfen += 1
  else: psnu += 1
ans = 'Fennec' if pfen > psnu else 'Snuke'
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### 木の読み込み tree

# サイズが大きいとdefaultdictが早い(for文を書かなくて済む)
from collections import defaultdict
n = int(input())
ns = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)
    
### BFS 幅優先探索

def bfs(start):
    from collections import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = d + 1
                q.appendleft(v)
    return seen
d1 = bfs(0)
d2 = bfs(n-1)
v = sum(d1[i]<=d2[i] for i in range(n))
v2 = n-v
if v>v2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### 木の読み込み tree

# サイズが大きいとdefaultdictが早い(for文を書かなくて済む)
from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    
### BFS 幅優先探索

def bfs(start):
    from collections import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = d + 1
                q.appendleft(v)
    return seen
d1 = bfs(0)
d2 = bfs(n-1)
v = sum(d1[i]<=d2[i] for i in range(n))
v2 = n-v
if v>v2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
def input():
    return stdin.readline().strip()

setrecursionlimit(10**5)

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

# root: 0
# edge1: parent→children
# edge2: child→parent
# tfに探索済かどうかを保存する
tf = [False] * n
tf[0] = True
edge1 = [[] for _ in range(n)]
edge2 = [-1] * n

def divide(i):
    for j in edge[i]:
        if tf[j]:
            continue
        else:
            tf[j] = True
            edge1[i].append(j)
            edge2[j] = i
            divide(j)

divide(0)

now = n - 1
l = [n-1]
while edge2[now] != -1:
    now = edge2[now]
    l.append(now)

root = l[len(l)//2 - 1]

def divide2(i):
    ans = 1
    for j in edge1[i]:
        ans += divide2(j)
    return ans

Snuke = divide2(root)
Fennec = n - Snuke

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
def input():
    return stdin.readline().strip()

setrecursionlimit((10**5) * 2)

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

# root: 0
# edge1: parent→children
# edge2: child→parent
# tfに探索済かどうかを保存する
tf = [False] * n
tf[0] = True
edge1 = [[] for _ in range(n)]
edge2 = [-1] * n

def divide(i):
    for j in edge[i]:
        if tf[j]:
            continue
        else:
            tf[j] = True
            edge1[i].append(j)
            edge2[j] = i
            divide(j)

divide(0)

now = n - 1
l = [n-1]
while edge2[now] != -1:
    now = edge2[now]
    l.append(now)

root = l[len(l)//2 - 1]

def divide2(i):
    ans = 1
    for j in edge1[i]:
        ans += divide2(j)
    return ans

Snuke = divide2(root)
Fennec = n - Snuke

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

Submission status: Accepted

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 "Snuke")

Submission status: Accepted

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)]
dis_f = [0 for i in range(n + 1)]
dis_s = [0 for i in range(n + 1)]
queue = collections.deque([1])
while queue:
    test = queue.popleft()
    flag[test] = True
    for i in graph[test]:
        if flag[i] == False:
            queue.append(i)
            dis_f[i] = dis_f[test] + 1
queue2 = collections.deque([n])
while queue2:
    test = queue2.popleft()
    flag2[test] = True
    for i in graph[test]:
        if flag2[i] == False:
            queue2.append(i)
            dis_s[i] = dis_s[test] + 1
count_f = 0
count_s = 0
for i in range(n):
    if dis_f[i + 1] <= dis_s[i + 1]:
        count_f += 1
    else:
        count_s += 1
if count_f > count_s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
ans = [0] * n
ans[0] = 1
ans[-1] = -1
Q = deque([0, n - 1])
while Q:
    p = Q.popleft()
    cur = ans[p]
    for v in edges[p]:
        if ans[v] == 0:
            ans[v] = cur
            Q.append(v)
if ans.count(1) > ans.count(-1):
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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
# なんでans=>0じゃないん？？？？？？？？？？？？？？？？？？
# > 手番のプレイヤーがマスに色を塗ることができなかったとき、敗者となります。
# あー総合の数じゃなかったわ...
print("Fennec" if ans > 0 else "Snuke")

Submission status: Accepted

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
# なんでans>=0じゃないん？？？？？？？？？？？
print("Fennec" if ans > 0 else "Snuke")

Submission status: Accepted

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

color = N*[0]
color[0] = 1
color[N-1] = -1
q = deque([])
q.append(0)
q.append(N-1)

while q:
  node = q.popleft()
  c = color[node]
  for to in G[node]:
    if color[to]==0:
      color[to] = c
      q.append(to)

b = color.count(1)
w = color.count(-1)

if w<b:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

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: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy

def solve():
    n = getN()
    g = [[] for i in range(n)]

    for i in range(n - 1):
        a, b = getZList()
        g[a].append(b)
        g[b].append(a)

    cf = [INF for i in range(n)]
    cf[0] = 0
    cs = [INF for i in range(n)]
    cs[-1] = 0

    d = deque()
    d.append(0)
    while d:
        cur = d.popleft()
        cc = cf[cur]
        for nx in g[cur]:
            if cf[nx] > cc + 1:
                cf[nx] = cc + 1
                d.append(nx)

    d = deque()
    d.append(n-1)
    while d:
        cur = d.popleft()
        cc = cs[cur]
        for nx in g[cur]:
            if cs[nx] > cc + 1:
                cs[nx] = cc + 1
                d.append(nx)

    pf, ps = 0, 0
    for i in range(n):
        if cf[i] <= cs[i]:
            pf += 1
        else:
            ps += 1

    if pf > ps:
        print("Fennec")
    else:
        print("Snuke")
    return


def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
f_dist = [-1]*(N+1)
s_dist = [-1]*(N+1)
G = [[] for _ in range(N+1) ]
for _ in range(N-1):
    x, y = map(int,readline().split())
    G[x].append(y)
    G[y].append(x)
    
def dfs(q,dist):       
    while q:
        x = q.popleft()
        for nx in G[x]:
            if dist[nx] != -1:
                continue
            dist[nx] = dist[x] + 1
            q.append(nx)

q = deque([1])
f_dist[1] = 0
dfs(q,f_dist)
q = deque([N])
s_dist[N] = 0
dfs(q,s_dist)
f_cnt = 0
s_cnt = 0
for i in range(1,N+1):
    if f_dist[i] <= s_dist[i]:
        f_cnt += 1
    else:
        s_cnt += 1
if f_cnt > s_cnt:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
M = N - 1
graph = [[] for _ in range(N + 1)]
dis_f = []
dis_s = []
#フェネックの距離
for i in range(M):
    a,b = map(int,input().rstrip().split(" "))
    graph[a].append(b)
    graph[b].append(a)

dist_f = [-1] * (N + 1)
dist_f[0] = 0
dist_f[1] = 0
d = deque()
d.append(1)
left = N -1
while(d):
    v = d.popleft()
    for i in graph[v]:
        if dist_f[i] != -1:
            continue
        dist_f[i] = dist_f[v] + 1
        d.append(i)
    
#すぬけくんの距離

dist = [-1] * (N + 1)
dist[0] = 0
dist[N] = 0
d = deque()
d.append(N)
while(d):
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)

count_f = 0
count_s = 0
for i in range(N):
    if(dist_f[i + 1] <= dist[i + 1]):
        count_f += 1
    else:
        count_s += 1
if(count_f > count_s):
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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]]
  pre = [0]*N
  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])
        pre[v] = u
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num, pre

d1, _, pre1 = dijkstra(0)
d2, _, pre2 = 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: Accepted

Solution code:
from collections import deque

N = int(input())
line = [[] for _ in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    line[u-1].append(v-1)
    line[v-1].append(u-1)

not_visited = [-1]*N
not_visited[0] = 0
stack = deque()
stack.append(0)

while stack != deque([]):
    now = stack.popleft()
    for i in line[now]:
        if not_visited[i] == -1:
            not_visited[i] = now
            stack.append(i)

route = []
now = N-1
while not_visited[now] != 0:
    route.append(now)
    now = not_visited[now]
route.append(now)
route.reverse()

l = len(route)

not_visited = [-1]*N
for i in route[l//2:]:
    not_visited[i] = -2
not_visited[0] = 0
stack = deque()
stack.append(0)

F = 0
while stack != deque([]):
    now = stack.popleft()
    for i in line[now]:
        if not_visited[i] == -1:
            not_visited[i] = not_visited[now] + 1
            stack.append(i)
            F += 1

S = N-F-2

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

Submission status: Accepted

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 "Snuke")


if __name__ == '__main__':
    main()

Submission status: Accepted

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)
def bfs(source, adj):
	q = collections.deque([(source,0)])
	distance = {}
	vis = set([source])
	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))
	return distance
a,b = bfs(1, adj), bfs(n, adj)
print 'Fennec' if 2* sum([+1 if a[u] <= b[u] else 0 for u in range(1, n+1)]) > n else 'Snuke'

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
G=[[] for _ in range(N+1)]

for i in range(N-1):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)
  
def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque()
    seen[s]=1
    todo.append(s)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d
  
d_f = bfs(1)
d_s = bfs(N)

count_f,count_s=0,0
for i in range(1,N+1):
  if d_f[i] <= d_s[i]:count_f +=1
  else: count_s += 1
    
if count_f>count_s:print('Fennec')
else:print('Snuke')

Submission status: Accepted

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: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge):

    search = [-1] * N
    search[v0] = 0
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if search[nv] == -1:
                q.append(nv)
                search[nv] = search[v] + 1

    return search


def bfs2(N, v0, edge, dis):

    q = deque()
    q.append(v0)

    ret = []

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if dis[v] > dis[nv] and dis[nv] != 0:
                q.append(nv)
                ret.append(nv)

    return ret[::-1]


def bfs3(N, v0, edge, color, x):

    search = [False] * N
    search[v0] = True
    q = deque()
    q.append(v0)

    ret = 0

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if not search[nv]:
                if color[nv] == -1:
                    ret += 1
                    q.append(nv)
                elif color[nv] == x:
                    q.append(nv)
                search[nv] = True

    return ret


def main():

    N = in_n()
    edge = [[] for _ in range(N)]

    for i in range(N - 1):
        a, b = in_nn()
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    dis = bfs(N, 0, edge)
    color_v = bfs2(N, N - 1, edge, dis)

    color = [-1] * N
    color[0] = 1
    color[-1] = 0

    color_v = deque(color_v)
    teban = 1

    while color_v:

        if teban == 1:
            v = color_v.popleft()
            color[v] = 1
            teban = 0

        elif teban == 0:
            v = color_v.pop()
            color[v] = 0
            teban = 1

    fen = bfs3(N, 0, edge, color, 1)
    sun = bfs3(N, N - 1, edge, color, 0)

    # print(color, fen, sun)

    if teban == 1:
        if fen > sun:
            ans = 'Fennec'
        else:
            ans = 'Snuke'
    elif teban == 0:
        if sun > fen:
            ans = 'Snuke'
        else:
            ans = 'Fennec'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


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

    """
    改良コードも試す。
    どっちが先にマスに色を塗るかは、要は両者のスタート地点からの距離を比べれば良い。
    前にもこの手の議論見た気がする。。。
    """

    # FennecとSnukeからのdepthを求める
    depth_from_Fennec = [-1] * N
    depth_from_Snuke = [-1] * N
    depth_from_Fennec[0] = 0
    depth_from_Snuke[N - 1] = 0

    q = deque([0])
    while q:
        u = q.popleft()
        for v in repn[u]:
            if depth_from_Fennec[v] != -1: continue
            depth_from_Fennec[v] = depth_from_Fennec[u] + 1
            q.append(v)
    q.append(N - 1)
    while q:
        u = q.popleft()
        for v in repn[u]:
            if depth_from_Snuke[v] != -1: continue
            depth_from_Snuke[v] = depth_from_Snuke[u] + 1
            q.append(v)

    Fennec = Snuke = 0
    for f, s in zip(depth_from_Fennec, depth_from_Snuke):
        if f <= s:
            Fennec += 1
        else:
            Snuke += 1
    if Fennec > Snuke:
        print("Fennec")
    else:
        print("Snuke")


if __name__ == "__main__":
    main()