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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  

s = 0

d1 = [INF]*N
d1[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d1[v] != INF: continue
    d1[v] = d1[u] + 1
    q.append(v)
    
s = N-1
d2 = [INF]*N
d2[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d2[v] != INF: continue
    d2[v] = d2[u] + 1
    q.append(v)
    
ans = 0
for i in range(N):
  if d1[i]<=d2[i]:
    ans += 1

if ans >= -(-(N+1)//2):
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
def dijkstra(s, stop, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))
            if u == stop:
                break

    return prev, cost


def main():
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk, cost = dijkstra(n, 1, g)
    l = cost[1] - 1
    k = l // 2 if l % 2 == 0 else l // 2 + 1
    vis = [False] * (n + 1)

    def f(now):
        if vis[now]:
            return 0
        vis[now] = True
        c = 1
        for _, nxt in g[now]:
            c += f(nxt)

        return c

    nw = dk[1]

    cnt = []
    i = 0
    vis[1] = True
    vis[n] = True
    while i < k:
        i += 1
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    fn += sum(cnt)
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dijkstra(s, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev, cost


def main():
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk, cost = dijkstra(n, g)
    l = cost[1] - 1
    k = l // 2 if l % 2 == 0 else l // 2 + 1
    vis = [False] * (n + 1)

    def f(now):
        if vis[now]:
            return 0
        vis[now] = True
        c = 1
        for _, nxt in g[now]:
            c += f(nxt)

        return c

    nw = dk[1]

    cnt = []
    i = 0
    vis[1] = True
    vis[n] = True
    while i < k:
        i += 1
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    fn += sum(cnt)
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dijkstra(s, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev


def main():
    from itertools import accumulate
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk = dijkstra(n, g)

    vis = [False] * (n + 1)

    def f(now, c):
        if vis[now]:
            return 0
        vis[now] = True
        cnt = 1
        for _, nxt in g[now]:
            cnt += f(nxt, c)

        return cnt

    nw = dk[1]

    cnt = []
    vis[1] = True
    vis[n] = True
    while nw != n:
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw, 0)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    *a, = accumulate(cnt)
    l = len(a)
    k = l // 2 - 1 if l % 2 == 0 else l // 2
    fn += a[k] if l > 0 else 0
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 木なので、任意の2点を結ぶルートはただ1つだけ存在する
# 最初にそこを順に埋めるのが最適。後は自分の陣営を埋めていく。
# 問題：点1→点Nのルートをどう求める? →幅優先探索かなぁ。

# 幅優先探索を2回やる必要がありそう
# 1回目で点1→点Nのルートを辿る。各点で1つ前の点をメモ。点Nから点1に逆にたどり、距離が半分の点Pを記録する
# 2回めでもう一度点1から辿る、点Pから先は探索しない（Snukeに取られる部分）。探索できた地点数が半分以上か否かを調べる

from collections import deque

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

neighbor = [[] for i in range(n)]
for e in edges:
    neighbor[e[0] - 1].append(e[1] - 1)
    neighbor[e[1] - 1].append(e[0] - 1)
    # 1-index → 0-index

info = [(-1, -1)] * n
info[0] = (0, -1) # 点1からの距離, 1つ点1寄りの点の番号

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

# 1回目
while True:
    v = q.popleft()
    distance = info[v][0]
    for nei in neighbor[v]:
        if info[nei][0] < 0:
            q.append(nei)
            info[nei] = (distance + 1, v)
    if len(q) == 0:
        break

# print(info)

# 点1〜点Nの距離が 10の場合、先手は5まで行ける。11の場合、5まで行ける。
# 逆に辿る
now = n-1
distance = info[n-1][0]
half = distance // 2

if distance == half + 1:
    # distance = 1の場合
    snuke_side_marginal = now
else:
    while True:
        now = info[now][1]
        distance -= 1
        if distance == half + 1:
            snuke_side_marginal = now
            break

# print(snuke_side_marginal)

info = [(-1, -1)] * n
info[0] = (0, -1) # 点1からの距離, 1つ点1寄りの点の番号

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

n_visited = 1
# 2回目

while True:
    v = q.popleft()
    distance = info[v][0]
    for nei in neighbor[v]:
        if info[nei][0] < 0 and nei != snuke_side_marginal:
            q.append(nei)
            info[nei] = (distance + 1, v)
            n_visited += 1

    if len(q) == 0:
        break

if n_visited > n - n_visited:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]
    adjlist = {}
    for a, b in AB:
        adjlist.setdefault(a-1, [])
        adjlist.setdefault(b-1, [])
        adjlist[a-1].append(b-1)
        adjlist[b-1].append(a-1)
    import collections
    q = collections.deque([0])
    sources = [None for _ in range(N)]
    sources[0] = -1
    while q:
        v = q.popleft()
        for nxt in adjlist[v]:
            if sources[nxt] is None:
                sources[nxt] = v
                q.append(nxt)
    
    # print(adjlist)
    # print(sources)
    shortest = [N-1]
    cur = N-1
    while True:
        shortest.append(sources[cur])
        if sources[cur] == 0:
            break
        cur = sources[cur]
    shortest.reverse()
    # print(shortest)
    shortest = collections.deque(shortest[1:-1])

    b_nexts = set(adjlist[0])
    b_nexts.discard(N-1)
    w_nexts = set(adjlist[N-1])
    w_nexts.discard(0)

    colored = [False for _ in range(N)]
    colored[0] = True
    colored[N-1] = True
    b_turn = True
    while True:
        # print(colored)
        # print(b_nexts)
        # print(w_nexts)
        # print(shortest)
        if b_turn:
            if len(b_nexts) == 0:
                print("Snuke")
                return
            if len(shortest) > 0:
                nxt = shortest.popleft()
                b_nexts.remove(nxt)
            else:
                nxt = b_nexts.pop()
            if nxt in w_nexts:
                w_nexts.remove(nxt)
        else:
            if len(w_nexts) == 0:
                print("Fennec")
                return
            if len(shortest) > 0:
                nxt = shortest.pop()
                w_nexts.remove(nxt)
            else:
                nxt = w_nexts.pop()
            if nxt in b_nexts:
                b_nexts.remove(nxt)
        # print(nxt)
        colored[nxt] = True
        for v in adjlist[nxt]:
            if colored[v] is False:
                if b_turn:
                    b_nexts.add(v)
                else:
                    w_nexts.add(v)
        
        b_turn = not b_turn
    #print("Snuke" if b_turn else "Fennec")


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
n=int(input())
ki=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  ki[a].append(b)
  ki[b].append(a)
# 0とn-1の最短ルートのうち0側に属するものn-1側に属するもの
from collections import deque
d_from_b=[-1]*n
d_from_w=[-1]*n
d_from_b[0]=0
todo=deque([0])
while todo:
  t=todo.popleft()
  l=ki[t]
  for li in l:
    if d_from_b[li]==-1:
      d_from_b[li]=d_from_b[t]+1
      todo.append(li)

d_from_w[n-1]=0
todo=deque([n-1])
while todo:
  t=todo.popleft()
  l=ki[t]
  for li in l:
    if d_from_w[li]==-1:
      d_from_w[li]=d_from_w[t]+1
      todo.append(li)
b_cnt=0
for i in range(n):
  if d_from_b[i]<=d_from_w[i]:
    b_cnt+=1
if n-b_cnt<b_cnt:
  print('Fennec')
else:
  print('Snuke')
#print(root)
#print(d_from_b,d_from_w)

Submission status: Accepted

Solution code:
n=int(input())
ki=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  ki[a].append(b)
  ki[b].append(a)
# 0とn-1の最短ルートのうち0側に属するものn-1側に属するもの
from collections import deque
# seen[i]:0からの最短ルートでiの一つ前の頂点
seen=[-2]*n
seen[0]=-1
todo=deque([0])
while todo:
  t=todo.popleft()
  l=ki[t]
  for li in l:
    if seen[li]==-2:
      seen[li]=t
      todo.append(li)
      if li==n-1:
        break
root=[n-1]
now=n-1
while now!=0:
  root.append(seen[now])
  now=seen[now]
bend=root[(len(root)-2)//2+1]
wend=root[(len(root)-2)//2]
# 頂点数数え
seen=[0]*n
seen[bend]=1
seen[wend]=1
todo=[bend]
cnt=0
while todo:
  t=todo.pop()
  l=ki[t]
  cnt+=1
  for li in l:
    if seen[li]==0:
      todo.append(li)
      seen[li]=1
if n-cnt<cnt:
  print('Fennec')
else:
  print('Snuke')
#print(root)
#print(bend,wend)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

dist1 = [-1]*n
dist1[0] = 0
dist2 = [-1]*n
dist2[n-1] = 0
def dfs(now,dist):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        dfs(nxt,dist)
dfs(0,dist1)
dfs(n-1,dist2)

fennec = snuke = 0
for i in range(n):
    if dist1[i] <= dist2[i]: fennec += 1
    else: snuke += 1
print("Fennec" if fennec > snuke else "Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

dist = [(0,-1) for _ in range(n)]
def dfs(now,prev=-1):
    for nxt in G[now]:
        if nxt == prev: continue
        dist[nxt] = (dist[now][0]+1,now)
        dfs(nxt,now)
dfs(0)

color = ["?"]*n
cnt = 0
now = n-1
w = (dist[n-1][0]+1)//2
while now != -1:
    if cnt < w: color[now] = -1
    else: color[now] = 1
    cnt += 1
    now = dist[now][1]

def coloring(now,prev=-1):
    for nxt in G[now]:
        if nxt == prev: continue
        if color[nxt] != "?" and color[now] != color[nxt]: continue
        color[nxt] = color[now]
        coloring(nxt,now)
coloring(0)
coloring(n-1)

print("Fennec" if sum(color) > 0 else "Snuke")

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())

Map = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    Map[a-1].append(b-1)
    Map[b-1].append(a-1)
INF = float('inf')
def distance(st):
    d = [INF for i in range(n)]
    d[st] = 0
    q = deque()
    q.append(st)
    while q:
        index = q.pop()
        for nexts in Map[index]:
            if d[nexts] == INF:
                d[nexts] = d[index]+1
                q.append(nexts)
    return d
d1 = distance(0)
d2 = distance(n-1)

fen = 0
snu = 0
for i in range(n):
    if d1[i]<= d2[i]:
        fen += 1
    else:
        snu += 1

if fen>snu:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    E = []
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        G[b].append(a)
        E.append((a, b))
    par = [-1] * N
    par[N - 1] = N - 1
    stk = [N - 1]
    while stk:
        v = stk.pop()
        for to in G[v]:
            if par[to] >= 0:
                continue
            par[to] = v
            stk.append(to)
    path = []
    v = 0
    while v != N - 1:
        path.append(v)
        v = par[v]
    path.append(N - 1)
    m = (len(path) - 1) // 2
    x, y = path[m], path[m + 1]
    uf = UnionFindTree(N)
    for a, b in E:
        if a == x and b == y or a == y and b == x:
            continue
        uf.union(a, b)
    print('Fennec' if uf.size(0) > uf.size(N - 1) else 'Snuke')

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

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

d1 = [-1] * n
d2 = [-1] * n
d1[0] = 0
d2[-1] = 0

q1 = deque([0])
q2 = deque([n-1])

while q1:
    l = q1.pop()
    for i in roots[l]:
        if d1[i] == -1:
            d1[i] = d1[l] + 1
            q1.append(i)

while q2:
    l = q2.pop()
    for i in roots[l]:
        if d2[i] == -1:
            d2[i] = d2[l] + 1
            q2.append(i)

f = 0
s = 0

for i in range(n):
    if d1[i] <= d2[i]:
        f += 1
    else:
        s += 1

if f > s:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque
def bfs(G, n,visited):
    q = deque([(1,'fe'),(n,'su')])
    visited[1] = 'fe'
    visited[n] = 'su'
    while q:
        curr_node = q.popleft()
        for next_node in G[curr_node[0]]:
            if visited[next_node] != 'yet': continue
            visited[next_node] = curr_node[1]
            q.append((next_node,curr_node[1]))


n = int(input())
G = [ [] for _ in range(n+1)]
visited = ['yet'] * (n+1)
for i in range(n-1):
    a, b = map(int, input().split()) 
    G[a].append(b)
    G[b].append(a)
bfs(G, n, visited)

if visited.count('fe') > visited.count('su'):
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())

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


def bfs(i):
    visited = [-1 for _ in range(N)]
    visited[i] = 0
    que = deque([(i, 0)])

    while que:
        ci, d = que.popleft()

        for ni in G[ci]:
            if visited[ni] == -1:
                visited[ni] = d+1
                que.append((ni, d+1))

    return visited


F = bfs(0)
S = bfs(N-1)


ans = 0
for i in range(N):
    if F[i] <= S[i]:
        ans += 1
    else:
        ans -= 1
if ans > 0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
n=int(input())

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

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

ans=[0]*n
ans[0]="B"
ans[n-1]="W"

from collections import deque

stack = deque([0,n-1])

while len(stack)>1:
    tmp=stack.popleft()

    for item in tree[tmp]:
        if ans[item]==0:
            if ans[tmp]=="W":
                ans[item]="W"
            else:
                ans[item]="B"
            stack.append(item)

if ans.count("B")>ans.count("W"):
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            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 cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

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



#52-

n = int(input())
nb = [[]for i in range(n)]

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

queue = [0,n-1]
done=0
col = [-1]*n
col[0]=0
col[n-1]=1

while(len(queue)>done):
    now = queue[done]
    done+=1
    for i in nb[now]:
        if(col[i]==-1):
            queue.append(i)
            col[i] = col[now]

print("Fennec" if n-sum(col) > sum(col) else "Snuke")

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
g = [[] for i in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
a = [-1]*N
b = [-1]*N
def bfs(n):
  q=deque()
  q.append(n)
  a[n] = 0
  while len(q):
    x=q.popleft()
    for i in g[x]:
      if a[i]==-1: 
        a[i]=a[x]+1
        q.append(i)
bfs(0)
def bfs2(n):
  q=deque()
  q.append(n)
  b[n] = 0
  while len(q):
    x=q.popleft()
    for i in g[x]:
      if b[i]==-1: 
        b[i]=b[x]+1
        q.append(i)
bfs2(N-1)
cnt = 0
for i in range(N):
  if a[i] <= b[i]:
    cnt += 1
  else:
    cnt -= 1
if cnt > 0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
f = 0
s = 0
from collections import deque
ps = [-1] * n
used = [False] * n
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    a = q.popleft()
    if a == n-1:
        break
    for u in edges[a]:
        if not used[u]:
            ps[u] = a
            q.append(u)
            used[u] = True

nx = n - 1
xs = [n-1]
while nx != 0:
    nx = ps[nx]
    xs.append(nx)

xs.reverse()
l = len(xs) - 2
f = (l+1)//2
s = l-f

if len(xs) == 2:
    z_lim = -1
    n_lim = 0
else:
    z_lim = (len(xs)+1)//2
    n_lim = z_lim - 1

# bfs 0側
used = [-1] * n
used[0] = 0 
q = deque([0])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[z_lim]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
f += cnt

# bfs n-1側
used = [-1] * n
used[n-1] = 0 
q = deque([n-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[n_lim]:
            q.append(u)
            used[u] = 0
            cnt += 1

s += cnt
# print("z_lim",z_lim,"nlim",n_lim)
# print("f",f,"s",s)
if f > s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

G = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
pars = [-1] * N
pars[0] = 0
stack = deque([0])
visited = [False] * N
visited[0] = True

while stack:
  now = stack.pop()
  for nxt in G[now]:
    if visited[nxt]:
      continue
    visited[nxt] = True
    pars[nxt] = now
    stack.append(nxt)

now = N-1
roads = []
while now != 0:
  now = pars[now]
  roads.append(now)

roads.reverse()
roads.append(N-1)
stack = deque([])
for i in range((len(roads)+1)//2):
  stack.append(roads[i])

stop = roads[(len(roads)+1)//2]
visited = [False] * N
for i in roads:
  visited[i] = True

black = (len(roads)+1)//2

while stack:
  now = stack.pop()
  for nxt in G[now]:
    if visited[nxt] or (nxt==stop):
      continue
    visited[nxt] = True
    stack.append(nxt)
    black += 1

white = N - black
if black > white:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
n=int(input())
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
fe=[0]*n
sn=[0]*n
from collections import deque
d=deque()
d.append(0)
visited=[False]*n
visited[0]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    fe[i]=fe[g]+1
d=deque()
d.append(n-1)
visited=[False]*n
visited[n-1]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    sn[i]=sn[g]+1
x=0
for i in range(n):
  if fe[i]>sn[i]:
    x+=1
  else:
    x-=1
print('Fennec' if x<0 else 'Snuke')

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    buf = sys.stdin.buffer
    
    n = int(buf.readline())
    E = map(int, (buf.read().split()))
    edges = [[] for i in range(n)]
    
    for a, b in zip(E, E):
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    
    todo = deque([0, n-1])
    
    colors = [0] * n
    colors[0] = 1
    colors[-1] = 2
    
    while todo:
        node = todo.popleft()
        color = colors[node]
    
        for to in edges[node]:
            if colors[to]:
                continue
            else:
                colors[to] = color
                todo.append(to)
    
    fennec_count = colors.count(1)
    if fennec_count > n // 2:
        print('Fennec ')
    
    else:
        print('Snuke ')


if __name__ == '__main__':
    main()

Submission status: Accepted

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


n = int(input())
edges = [[] for i in range(n)]

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

todo = deque([(0, 1), (n-1, 2)])

colors = [0] * n
colors[0] = 1
colors[-1] = 2

while todo:
    node, color = todo.popleft()
    for to in edges[node]:
        if colors[to]:
            continue
        else:
            colors[to] = color
            todo.append((to, color))

fennec_count = colors.count(1)
if fennec_count > n // 2:
    print('Fennec ')

else:
    print('Snuke ')