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:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        xの属する木の根を返す
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        x, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

    """
    まさかの問題を読み間違えていた。。。
    （プレイヤーがマスの上を１マスずつ動くと思っていた）

    「最適に行動した時」＝「どちらかに必勝法が存在する」と言い換える。
    あとはその戦略を見出せば勝ち。見抜けなければ相手の全行動パターンに勝つ手の存在を示す。
    同じ色が隣接していればどのマスでも塗れるなら、最初に一気に２人が距離を詰めた方がいいに決まってる。
    """

    # 頂点０からのdepthを求める
    depth_from_0 = [-1] * N
    parent = [-1] * N
    depth_from_0[0] = 0

    def dfs(u):
        for v in repn[u]:
            if depth_from_0[v] != -1: continue
            depth_from_0[v] = depth_from_0[u] + 1
            parent[v] = u
            dfs(v)

    dfs(0)

    # ２人を結ぶパスの同定
    path = [N - 1]
    while path[-1] != 0: path.append(parent[path[-1]])
    l = len(path)

    # ２人が互いに塗るマスの数を計算
    tree = UnionFind(N)
    a0, b0 = path[l // 2 - 1], path[l // 2]
    if a0 > b0: a0, b0 = b0, a0
    for a, b in edge:
        if a != a0 or b != b0: tree.union(a, b)
    Fennec = tree.size(0)
    Snuke = tree.size(N - 1)
    if Fennec > Snuke:
        print("Fennec")
    else:
        print("Snuke")



if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bfs(s):
    q = deque([s])
    dist = [-1]*N
    dist[s] = 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
        
    return dist

N = int(input())
G = [[] for _ 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)

d1 = bfs(0)
d2 = bfs(N-1)
c = 0

for i in range(N):
    if d1[i]<=d2[i]:
        c += 1

if c>N-c:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

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

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

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

p = p[::-1]
t = p[-(-len(p)//2)-1]

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

Submission status: Accepted

Solution code:
import queue
n=int(input())
e=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=queue.Queue()
q.put(1)
vif=[-1]*n
vif[0]=0
while not q.empty():
  now=q.get()
  for to in e[now]:
    if vif[to-1]==-1:
      q.put(to)
      vif[to-1]=vif[now-1]+1
q.put(n)
vis=[-1]*(n+1)
vis[n-1]=0
while not q.empty():
  now=q.get()
  for to in e[now]:
    if vis[to-1]==-1:
      q.put(to)
      vis[to-1]=vis[now-1]+1
ans=0
for i in range(n):
  if vif[i]<=vis[i]:ans+=1
print(['Snuke','Fennec'][ans>n//2])

Submission status: Accepted

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


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces

def make_tree_0index(N):
    edge_dic = {}
    for _ in range(N-1):
        x, y = na()
        x -= 1
        y -= 1
        if x in edge_dic:
            edge_dic[x].append(y)
        else:
            edge_dic[x] = [y]
        if y in edge_dic:
            edge_dic[y].append(x)
        else:
            edge_dic[y] = [x]
    return edge_dic


N = ni()

edge_dic = make_tree_0index(N)

parent_array = [-2] * N
depth_array = [-1] * N

node = deque([0])
parent_array[0] = -1
depth_array[0] = 0

while(len(node)):
    n = node.popleft()
    for nn in edge_dic[n]:
        if nn == parent_array[n]:
            continue
        parent_array[nn] = n
        depth_array[nn] = depth_array[n] + 1
        node.append(nn)

# print(parent_array,depth_array)

now_depth = depth_array[-1]
max_node = N - 1
for i in range((now_depth-1)//2):
    max_node = parent_array[max_node]

cnt = 1
node.append(max_node)
while(len(node)):
    n = node.popleft()
    for nn in edge_dic[n]:
        if nn == parent_array[n]:
            continue
        node.append(nn)
        cnt += 1

# print(cnt)

if cnt * 2 >= N:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()

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

Fennec = [-1]*(N+1)  # Fennec の各頂点への最短距離
Snuke = [-1]*(N+1)  # Snuke の各頂点への距離

from collections import deque

q1 = deque([1])
q2 = deque([N])
Fennec[1] = 0
Snuke[N] = 0
while q1:
    n = q1.pop()
    for d in Graph[n]:
        if Fennec[d] == -1:
            Fennec[d] = Fennec[n] + 1
            q1.appendleft(d)
while q2:
    n = q2.pop()
    for d in Graph[n]:
        if Snuke[d] == -1:
            Snuke[d] = Snuke[n] + 1
            q2.appendleft(d)
            
a = sum(Fennec[i] <= Snuke[i] for i in range(1,N+1))
print('Fennec' if a >= N//2+1 else 'Snuke')

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

def main():
  n=int(input())
  edges=[tuple(map(int,input().split())) for _ in range(n-1)]
  d=defaultdict(list)
  for e in edges:
    d[e[0]].append(e[1])
    d[e[1]].append(e[0])
  def dist(m):
    c=-1
    dl=[-1]*(n+1)
    cv=deque([m])
    nv=deque([1])
    while nv:
      c+=1
      cv.extend(nv)
      nv.clear()
      for e in cv:
        dl[e]=c
        for x in d[e]:
          if dl[x]<0:
            nv.append(x)
      cv.clear()
    return dl[1:]
  fnc=dist(1)
  snk=dist(n)
  j=sum([(fnc[i]<=snk[i])-(fnc[i]>snk[i]) for i in range(n)])
  if j>0:
    print('Fennec')
  else:
    print('Snuke')

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque

n=int(input())
edges=[tuple(map(int,input().split())) for _ in range(n-1)]
d=defaultdict(list)
for e in edges:
  d[e[0]].append(e[1])
  d[e[1]].append(e[0])
fnc=[-1]*(n+1)
snk=[-1]*(n+1)
fnc[1]=0
snk[n]=0
cv=deque([1])
nv=deque([1])
c=-1
while nv:
  c+=1
  cv.extend(nv)
  nv.clear()
  for e in cv:
    fnc[e]=c
    for x in d[e]:
      if fnc[x]<0:
        nv.append(x)
  cv.clear()
cv.append(n)
nv=deque([1])
c=-1
while nv:
  c+=1
  cv.extend(nv)
  nv.clear()
  for e in cv:
    snk[e]=c
    for x in d[e]:
      if snk[x]<0:
        nv.append(x)
  cv.clear()

j=sum([(fnc[i]<=snk[i])-(fnc[i]>snk[i]) for i in range(1,n+1)])
if j>0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    dist1 = [-1] * N
    dist1[0] = 0
    queue = deque([0])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist1[nv] == -1:
                dist1[nv] = dist1[v] + 1
                if nv != N - 1:
                    queue.append(nv)

    dist2 = [-1] * N
    dist2[N - 1] = 0
    queue = deque([N - 1])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist2[nv] == -1:
                dist2[nv] = dist2[v] + 1
                if nv != 0:
                    queue.append(nv)

    F = S = 0
    for i, (d1, d2) in enumerate(zip(dist1, dist2)):
        if i in (0, N - 1):
            continue
        if d1 == -1:
            S += 1
        elif d2 == -1:
            F += 1
        elif d1 <= d2:
            F += 1
        else:
            S += 1

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    dist = [f_inf] * n
    dist[0] = 0
    q = deque([0])
    while q:
        u = q.popleft()
        if u != n - 1:
            for nv in edge[u]:
                if dist[nv] == f_inf:
                    dist[nv] = dist[u] + 1
                    q.append(nv)

    half_dist = (dist[-1] - 1) // 2
    dist2 = [f_inf] * n
    dist2[-1] = 0
    q = deque([n - 1])
    while q:
        u = q.popleft()
        for nv in edge[u]:
            if dist[nv] == f_inf:
                continue
            else:
                if dist2[nv] == f_inf:
                    if dist2[u] + 1 <= half_dist:
                        dist2[nv] = dist2[u] + 1
                        q.append(nv)

    visited = [False] * n
    visited[0] = True
    q = deque([0])
    while q:
        u = q.popleft()
        if u != n - 1:
            for nv in edge[u]:
                if dist2[nv] == f_inf and not visited[nv]:
                    visited[nv] = True
                    q.append(nv)

    fennec = sum(visited)
    snuke = n - fennec
    print("Fennec" if fennec > snuke else "Snuke")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

color = [0]*N
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 b > w:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
cnt = [1, 1]
q = deque([(0, 0), (n-1, 1)])
seen = [False]*n
seen[0] = seen[n-1] = True
while q:
    node, turn = q.popleft()
    for c_node in graph[node]:
        if seen[c_node]:
            continue
        seen[c_node] = True
        cnt[turn] += 1
        q.append((c_node, turn))
print('FSennunkeec'[cnt[1]>=cnt[0]::2])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
pre = [None]*n
def dfs(node, p_node=-1):
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        pre[c_node] = node
        dfs(c_node, node)
dfs(0)
path = [n-1]
now = n-1
while now>0:
    now = pre[now]
    path.append(now)
snuke = path[len(path)//2-1]
fennec = path[len(path)//2]
def dfs2(node, p_node):
    cnt = 1
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        cnt += dfs2(c_node, node)
    return cnt
print('FSennunkeec'[dfs2(fennec, snuke)<=dfs2(snuke, fennec)::2])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
from collections import deque 
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
INF = 1 << 32
d = [INF] * n
d[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for e in es[v]:
        if d[e] == INF:
            d[e] = d[v] + 1
            q.append(e)
d2 = [INF] * n
q.append(n - 1)
d2[n - 1] = 0
while q:
    v = q.popleft()
    for e in es[v]:
        if d2[e] == INF and d2[v] + 1 < d[e]:
            d2[e] = d2[v] + 1
            q.append(e)

print("Fennec" if 2 * sum(1 for i in d2 if i < INF) < n else "Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
def dfs0(v, d, p):
    if v == n - 1:
        return d
    for e in es[v]:
        if e != p:
            k = dfs0(e, d + 1, v)
            if k:
                if isinstance(k, int) and k // 2 == d:
                    return v, e
                return k
    return 0

def dfs1(v, p):
    if v == E:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs1(e, v)
    return cnt

V, E = dfs0(0, 0, -1)
if  2*dfs1(0, -1) > n:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
def dfs0(v, d, p):
    if v == n - 1:
        return d
    for e in es[v]:
        if e != p:
            k = dfs0(e, d + 1, v)
            if k:
                if isinstance(k, int) and k // 2 == d:
                    return v, e
                return k
    return 0

def dfs1(v, p):
    if v == E:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs1(e, v)
    return cnt

def dfs2(v, p):
    if v == 0:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs2(e, v)
    return cnt
V, E = dfs0(0, 0, -1)
if  2*dfs1(0, -1) > n:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
def dfs0(v, d, p):
    if v == n - 1:
        return d
    for e in es[v]:
        if e != p:
            k = dfs0(e, d + 1, v)
            if k:
                if isinstance(k, int) and k // 2 == d:
                    return v, e
                return k
    return 0

def dfs1(v, p):
    if v == E:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs1(e, v)
    return cnt


V, E = dfs0(0, 0, -1)
if  2*dfs1(0, -1) > n:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from dataclasses import dataclass

def solve(N: int, a: "List[int]", b: "List[int]"):
    from collections import defaultdict, deque
    edges = defaultdict(list)
    for aa, bb in zip(a, b):
        edges[aa].append(bb)
        edges[bb].append(aa)
    def f():
        visited = [None] * (N+1)
        que = deque([("f", 1), ("s", N)])
        while que:
            name, node = que.popleft()
            if visited[node]:
                continue
            visited[node] = name
            for n in edges[node]:
                if visited[n]:
                    continue
                que.append((name, n))
        return sum("f" == v for v in visited)
    return "Fennec" if f() > N // 2 else "Snuke"
            


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, a, b))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
query = [[] for _ in range(N)]
ab = []
for _ in range(N-1):
    a, b = mapint()
    query[a-1].append(b-1)
    query[b-1].append(a-1)
    ab.append((a-1, b-1))

def dfs_lis(start):
    checked = [0]*N
    dist = [0]*N
    def dfs(now):
        checked[now] = 1
        for nx in query[now]:
            if not checked[nx]:
                dist[nx] = dist[now]+1
                dfs(nx)
    dfs(start)
    return dist

fe = dfs_lis(0)
snu = dfs_lis(N-1)
cnt = 0
for f, s in zip(fe, snu):
    if f<=s:
        cnt += 1

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

Submission status: Accepted

Solution code:
n=int(input())
g=[[] for _ in range(n+1)]

class tree:
    def __init__(self,n):
        self.size=n
        self.parent=[-1]*(n+1)
        self.child=[[] for _ in range(n+1)]
    
    def findparent(self,x):
        return self.parent[x]
    
    def append(self,p,x):
        self.parent[x]=p
        self.child[p].append(x)
    
    def retchild(self,p):
        return self.child[p]
        

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

    g[a].append(b)
    g[b].append(a)

t=tree(n)
stack=[1]
visited=[0]*(n+1)

while len(stack)>0:
    u=stack.pop()
    visited[u]=1

    for v in g[u]:
        if visited[v]==1:
            continue

        stack.append(v)
        t.append(u,v)

r=n
cnt=1
while t.findparent(r)>0:
    r=t.findparent(r)
    cnt+=1

tmpcnt=cnt//2-1
r=n
while tmpcnt>0:
    r=t.findparent(r)
    tmpcnt-=1

stack=[r]
rest=1

while len(stack)>0:
    u=stack.pop()
    rest+=len(t.retchild(u))

    for v in t.retchild(u):
        stack.append(v)

snu=rest-cnt//2
fen=n-rest-(cnt+1)//2

if (cnt%2==0 and fen>snu) or (cnt%2==1 and fen>=snu):
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
dist = [0 for _ in range(N+1)]
que = deque([(1,0)])
hist = [0 for _ in range(N+1)]
hist[1] = 1
while que:
    x,d = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            hist[y] = 1
            dist[y] = d+1
            que.append((y,d+1))
pa ={}
x = N
while x!=1:
    for y in G[x]:
        if dist[y]==dist[x]-1:
            pa[x] = y
            break
    x = pa[x]
ch = {}
x=N
while x!=1:
    y = pa[x]
    ch[y] = x
    x = y
if dist[N]%2==1:
    k = dist[N]//2
    cnt = 0
    x = 1
    y = N
    while cnt<k:
        x = ch[x]
        y = pa[y]
        cnt += 1
    G[x].remove(y)
    G[y].remove(x)
    hist = [0 for _ in range(N+1)]
    que = deque([1])
    hist[1] = 1
    while que:
        a = que.popleft()
        for b in G[a]:
            if hist[b]==0:
                hist[b]=1
                que.append(b)
    n1 = sum(hist)
    n2 = N-n1
    if n1>n2:
        print("Fennec")
    else:
        print("Snuke")
else:
    k = dist[N]//2
    cnt = 0
    x = 1
    while cnt<k:
        x = ch[x]
        cnt += 1
    y = ch[x]
    G[x].remove(y)
    G[y].remove(x)
    hist = [0 for _ in range(N+1)]
    que = deque([1])
    hist[1] = 1
    while que:
        a = que.popleft()
        for b in G[a]:
            if hist[b]==0:
                hist[b]=1
                que.append(b)
    n1 = sum(hist)
    n2 = N-n1
    if n1>n2:
        print("Fennec")
    else:
        print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


N = int(input())
G = [[] for _ in range(N)]
INPUT = []
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
  INPUT.append((a,b))
visit = set([])
path = [0]
def dfs(v):
  if v in visit:
    return
  visit.add(v)
  if v == N-1:
    return
  for w in G[v]:
    if w in visit:
      continue
    path.append(w)
    dfs(w)
    if path[-1] == N-1:
      return
    path.pop()
dfs(0)
#print(path)
if len(path)%2 == 0:
  A,B = path[len(path)//2-1],path[len(path)//2]
else:
  A,B = path[len(path)//2],path[len(path)//2+1]
#print(A,B)
uf = UnionFind(N)
for i in range(N-1):
  a,b = INPUT[i]
  if (a == A and b == B) or (a == B and b == A):
    continue
  uf.union(a,b)
fen = uf.get_size(0)
snu = uf.get_size(N-1)
if fen > snu:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
import collections
n=int(input())
graph=[]
for i in range(n+1):
  graph.append([])
for i in range(n-1):
  a,b=map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
dist1=[0]*(n+1)
distn=[0]*(n+1)
bfs=collections.deque([[1,0]])
visited=set()
while bfs:
  s=bfs.popleft()
  visited.add(s[0])
  dist1[s[0]]=s[1]
  for i in graph[s[0]]:
    if i in visited:
      continue
    bfs.append([i,s[1]+1])
bfs=collections.deque([[n,0]])
visited=set()
while bfs:
  s=bfs.popleft()
  visited.add(s[0])
  distn[s[0]]=s[1]
  for i in graph[s[0]]:
    if i in visited:
      continue
    bfs.append([i,s[1]+1])
score1=0
scoren=0
for i in range(1,n+1):
  if dist1[i]>distn[i]:
    scoren+=1
  else:
    score1+=1
if scoren>=score1:
  print('Snuke')
else:
  print('Fennec')

Submission status: Accepted

Solution code:
n = int(input())
g = [[]*(n) 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)
ds = [0]*n
de = [0]*n
from collections import deque
def bfs(s,d):
    q = deque()
    q.append((s,1))
    visit = [False]*n
    visit[s] = True
    cnt =1
    while q:
        s,p = q.popleft()
        if cnt==n: break
        for i in g[s]:
            if not visit[i]:
                d[i] = p
                visit[i] = True
                cnt += 1
                q.append((i,p+1))
bfs(0,ds)
bfs(n-1,de)
s,e=0,0
for i in range(n):
    if ds[i]<=de[i]:
        s+=1
    else:
        e+=1
if s>e:
    print('Fennec')
else:
    print('Snuke')