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: Time Limit Exceeded

Solution code:
#相手のパスを潰したい
# こちら側に来てほしくない場合,最短経路を潰すしか無い
# 最適を簡単に表せない A - B - C - D
#                EF-|   |-GH...
# のとき、A→EFとやっていると、Bを取られて死ぬ
# でもこれをいちいち計算できない
# 「相手のパスを潰す」、というのは、最短経路がより短いほうが勝つと考える?
# でも相手にパスが潰されるかどうかはわからない
# とりあえずやってみる

#初期点を分断しなきゃ
n = int(input())
INF = 10**6
graph = [[float("inf")]*n for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1][b -1] = 1
    graph[b - 1][a - 1] = 1

#ダイクストラで0, n-1からの最短距離を求める


import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))
d = Dijkstra()
#print(d.dijkstra(graph, start=0))
#print(d.dijkstra(graph, start=n-1))
keiro = d.dijkstra(graph, start=0, goal=n-1)
kiru = (len(keiro) + 1)//2 - 1
#print(keiro)
#print(keiro[kiru], keiro[kiru + 1])
graph[keiro[kiru]][keiro[kiru + 1]] = float("inf")
graph[keiro[kiru + 1]][keiro[kiru]] = float("inf")
#中心で分断
f = 0
s = 0
for i in d.dijkstra(graph, start=0):
    if i < float("inf"):
        f += 1
for j in d.dijkstra(graph, start=n-1):
    if j < float("inf"):
        s += 1
print("Fennec" if f > s else "Snuke")

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

n = raw_input()
n = int(n)

tree = []

i = 0
while i < n:
    tree.append([])
    i += 1

i = 0
while i < n-1:
    ab = raw_input()
    ab = ab.split()
    ab = map(int,ab)
    tree[ab[0]-1].append(ab[1])
    tree[ab[1]-1].append(ab[0])
    i += 1

black = [n]*n
white = [n]*n

black[0] = 0
white[n-1] = 0

i = 0
while max(black) >= n and max(white) >= n:
    black_next_list = []
    black_i_list = []
    while i in black:
        black_i = black.index(i)
        black_next_list.extend(tree[black_i])
        black[black_i] = n
        black_i_list.append(black_i)

    for black_i in black_i_list:
        black[black_i] = i

    for black_next in black_next_list:
        if black[black_next - 1] < i:
            pass
        else:
            black[black_next - 1] = i + 1

    white_next_list = []
    white_i_list = []
    while i in white:
        white_i = white.index(i)
        white_next_list.extend(tree[white_i])
        white[white_i] = n
        white_i_list.append(white_i)

    for white_i in white_i_list:
        white[white_i] = i

    for white_next in white_next_list:
        if white[white_next - 1] < i:
            pass
        else:
            white[white_next - 1] = i + 1

    i += 1

status = 0

i = 0
while i < n:
    if black[i] <= white[i]:
        status += 1
    else:
        status -= 1
    i += 1

if status > 0:
    print "Fennec"
else:
    print "Snuke"

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class mas_node():
    def __init__(self, now_number, pass_route):
        self.now_number = now_number
        self.pass_route = pass_route
        self.pass_route.append(now_number)

    def set_now_number(self, now_number):
        self.now_number = now_number
        self.pass_route.append(now_number)

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]

    adj_list = {}
    for i in range(N):
        adj_list[i + 1] = []

    for i in range(N - 1):
        input_raw = list(read_func().strip().split())
        adj_list[int(input_raw[0])].append(int(input_raw[1]))
        adj_list[int(input_raw[1])].append(int(input_raw[0]))


    node_list = [mas_node(1, [])]
    is_already_pass = [False] * N
    is_already_pass[0] = True
    while 1:
        new_node_list = []
        for m_node in node_list:
            for next_mass_number in adj_list[m_node.now_number]:
                if is_already_pass[next_mass_number - 1] == False:
                    new_m_node = copy.deepcopy(m_node)
                    new_m_node.set_now_number(next_mass_number)
                    new_node_list.append(new_m_node)
                    is_already_pass[next_mass_number - 1] = True;
                    if next_mass_number == N:
                        one_to_N_pass = copy.deepcopy(new_m_node)
        node_list = copy.deepcopy(new_node_list)
        if new_node_list == []:
            break;
    to_N_pass_route = deque(one_to_N_pass.pass_route)
    to_N_pass_route.popleft()
    to_N_pass_route.pop()
    already_colored_list = [False] * N
    mas_set = {}
    mas_set["b"] = [1]
    mas_set["w"] = [N]
    pass_len = len(to_N_pass_route)
    for i in range(pass_len):
        if len(to_N_pass_route) == 0:
            break;
        b = to_N_pass_route.popleft()
        already_colored_list[b - 1] = True
        mas_set["b"].append(b)
        if len(to_N_pass_route) == 0:
            break;
        w = to_N_pass_route.pop()
        already_colored_list[w - 1] = True
        mas_set["w"].append(w)

    black_mas_node = copy.deepcopy(mas_set["b"])
    white_mas_node = copy.deepcopy(mas_set["w"])
    while 1:
        new_black_mas_node = []
        for b_mas in black_mas_node:
            for next_b_mas in adj_list[b_mas]:
                if already_colored_list[next_b_mas - 1] == False:
                    mas_set['b'].append(next_b_mas)
                    new_black_mas_node.append(next_b_mas)
                    already_colored_list[next_b_mas - 1] = True
        black_mas_node = copy.deepcopy(new_black_mas_node)

        new_white_mas_node = []
        for w_mas in white_mas_node:
            for next_w_mas in adj_list[w_mas]:
                if already_colored_list[next_w_mas - 1] == False:
                    mas_set['w'].append(next_w_mas)
                    new_white_mas_node.append(next_w_mas)
                    already_colored_list[next_w_mas - 1] = True
        white_mas_node = copy.deepcopy(new_white_mas_node)

        if len(white_mas_node) == 0 & len(black_mas_node) == 0:
            break;

    if len(mas_set['b']) > len(mas_set['w']):
        print "Fennec"
    else:
        print "Snuke"



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import*
n=input();G=[[]for d in[deque([1,-1])]*-~n]
for C in[[0,1]+[0]*(n-2)+[2]]*~-n:a,b=map(int,raw_input().split());G[a]+=b,;G[b]+=a,
while d:
 v=d.popleft()
 for t in G[v]:exec"C[t]=C[v];d+=t,"*(C[t]<1)
print["Fennec","Snuke"][2*C.count(1)<=n]

Submission status: Time Limit Exceeded

Solution code:
import queue


class Edge:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class P:
    def __init__(self, distance, v):
        self.distance = distance
        self.v = v


def dijkstra(_s):
    que = queue.Queue()
    global d
    d = [float("inf") for i in range(N)]
    d[_s] = 0
    que.put(P(0, _s))

    while not que.empty():
        p = que.get()
        v = p.v
        if d[v] < p.distance:
            continue
        for i in range(0, len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                que.put(P(d[e.to], e.to))


if __name__ == '__main__':
    N = int(input())
    a = []
    b = []
    for i in range(N - 1):
        tmp_a, tmp_b = list(map(int, input().split()))
        a.append(tmp_a - 1)
        b.append(tmp_b - 1)

    G = [[] for i in range(N)]
    for i in range(0, N - 1):
        G[a[i]].append(Edge(b[i], 1))
        G[b[i]].append(Edge(a[i], 1))

    # Fennec
    global d
    dijkstra(0)
    Fennec_d = d

    # sunuke
    dijkstra(N - 1)
    sunuke_d = d

    for i in range(0, len(Fennec_d)):
        if Fennec_d[i] <= sunuke_d[i]:
            sunuke_d[i] = -1
        else:
            Fennec_d[i] = -1

    # print(Fennec_d)
    # print(sunuke_d)

    Fennec_count = 0
    sunuke_count = 0
    for i in range(0, len(Fennec_d)):
        if Fennec_d[i] < 0:
            sunuke_count += 1
        else:
            Fennec_count += 1

    if sunuke_count<Fennec_count:
        print("Fennec")
    else:
        print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
d = {}
for _ in range(n-1):
  v,u = map(int, raw_input().split())
  if v in d:
    d[v].append(u)
  else:
    d[v] = [u]

  if u in d:
    d[u].append(v)
  else:
    d[u] = [v]

visited = [False] * (n+1)
# 0 == fennec, 1 == sunuke
q = [(1,1,0), (n,n,1)]

count_f = 0
count_s = 0

while len(q) > 0:
  cur, prev, sunuke = q.pop(0)
  # print cur,prev,sunuke

  if visited[cur]:
    continue

  visited[cur] = True
  if sunuke:
    count_s += 1
  else:
    count_f += 1

  for v in d[cur]:
    q.append([v, cur, sunuke])

if count_f > count_s:
  print 'Fennec'
else:
  print 'Snuke'

Submission status: Accepted

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
x,y=map(eval(dir()[741]),[Graph(t)]*2,['1']+N)
print('FSennunkeec'[len(t)<sum(x[k]>y[k]for k in x)*2::2])

Submission status: Accepted

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
x,y=map(vars()[dir()[741]],[Graph(t)]*2,['1']+N)
print('FSennunkeec'[len(t)<sum(x[k]>y[k]for k in x)*2::2])

Submission status: Accepted

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
x,y=map(vars()[dir()[741]],[Graph(t)]*2,['1']+N)
print('FSennunkeec'[len(x)<=sum(x[k]>y[k]for k in x)*2::2])

Submission status: Accepted

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
x,y=map(vars()[dir()[741]],[Graph(t)]*2,['1',*N])
print('FSennunkeec'[len(x)<=sum(x[k]>y[k]for k in x)*2::2])

Submission status: Accepted

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
s=vars()[dir()[741]]
y=s(G:=Graph(t),*N)
print('FSennunkeec'[len(x:=s(G,'1'))<=sum(x[k]>y[k]for k in x)*2::2])

Submission status: Accepted

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
s=vars()[dir()[741]]
x=s(G:=Graph(t),'1')
y=s(G,*N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=len(x)::2])

Submission status: Accepted

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
s=shortest_path_length
x=s(G:=Graph(t),'1')
y=s(G,*N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=len(x)::2])

Submission status: Accepted

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
s=shortest_path_length
x=s(G:=Graph(t),'1')
y=s(G,*N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(*N)::2])

Submission status: Accepted

Solution code:
from networkx import*
(N,),*t=map(str.split,open(0))
x,y=[shortest_path_length(Graph(t),v)for v in('1',N)]
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Submission status: Accepted

Solution code:
from networkx import*
(N,),*t=map(str.split,open(0))
s=shortest_path_length
x=s(G:=Graph(t),'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Submission status: Accepted

Solution code:
from networkx import*
(N,),*t=map(str.split,open(0))
G=Graph(t)
s=shortest_path_length
x=s(G,'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Submission status: Accepted

Solution code:
from networkx import*
(N,),*t=map(str.split,open(0))
G=Graph()
G.add_edges_from(t)
s=shortest_path_length
x=s(G,'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Submission status: Accepted

Solution code:
from networkx import*
(N,),*t=[s.split()for s in open(0)]
G=Graph()
G.add_edges_from(t)
s=shortest_path_length
x=s(G,'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Submission status: Accepted

Solution code:
from networkx import*
N,*t=open(0)
G=Graph()
for s in t:a,b=s.split();G.add_edge(a,b)
s=shortest_path_length
x=s(G,'1')
y=s(G,N[:-1])
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Submission status: Accepted

Solution code:
from networkx import*
(N,),*t=[s.split()for s in open(0)]
G=Graph()
for a,b in t:G.add_edge(a,b)
s=shortest_path_length
x=s(G,'1')
y=s(G,N)
c=0
for k in y:c+=x[k]>y[k]
print('FSennunkeec'[c*2>=int(N)::2])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
def dfs(node,dist,distl):
    distl[node]=dist
    for e in edge[node]:
        if distl[e]==-1:
            dfs(e,dist+1,distl)
dista,distb=[-1]*n,[-1]*n
dfs(0,0,dista)
dfs(n-1,0,distb)
a,b=0,0
for i in range(n):
    if dista[i]<=distb[i]:
        a+=1
    else:
        b+=1
print('Fennec' if a>b else 'Snuke')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*ab = map(int,read().split())

m = iter(ab)
g = [[] for _ in range(n)]
for a,b in zip(m,m):
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dist(g,start):
    n = len(g)
    dist = [-1]*n
    q = [start]
    dist[start] = 0
    while q:
        v = q.pop()
        for c in g[v]:
            if dist[c] == -1:
                dist[c] = dist[v]+1
                q.append(c)
    return dist        

df = dist(g,0)
ds = dist(g,n-1)


cnt = 0
for i,j in zip(df,ds):
    if i <= j:
        cnt += 1
    else:
        cnt -= 1

#print(cnt)
if cnt >= 1:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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
    ans = 0
    q = deque([s, cnt])
    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: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque


def solve(N: int, path):
    f, s = [1], [N]
    black = set([1])
    white = set([N])
    while True:
        fn = []
        for ff in f:
            for fnext in path[ff]:
                if fnext not in white and fnext not in black:
                    black.add(fnext)
                    fn.append(fnext)
        f = fn
        sn = []
        for ss in s:
            for snext in path[ss]:
                if snext not in white and snext not in black:
                    white.add(snext)
                    sn.append(snext)
        s = sn
        if not s and not f:
            break
    print("Fennec" if len(black) > len(white) else "Snuke")
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    path = {}
    for i in range(N - 1):
        a = int(next(tokens))
        b = int(next(tokens))
        if a in path:
            path[a].append(b)
        else:
            path[a] = [b]
        if b in path:
            path[b].append(a)
        else:
            path[b] = [a]
    solve(N, path)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)


class Node:

    def __init__(self, num):
        self.num = num
        self.v = 1
        self.parent = 0
        self.deep = None


def LI():
    return list(map(int, input().split()))

# input
N = int(input())
AB = [LI() for _ in range(N - 1)]

# link
link = [[] for _ in range(N + 1)]
for a, b in AB:
    link[a].append(b)
    link[b].append(a)

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


def create_tree(parent):
    for child in link[parent.num]:
        if child == parent.parent:
            continue
        node = nodes[child]
        node.parent = parent.num
        node.deep = parent.deep + 1
        create_tree(node)
        parent.v += node.v


def main():
    nodes[1].deep = 1
    create_tree(nodes[1])

    x = (nodes[N].deep - nodes[1].deep - 1) // 2
    v = nodes[N]
    for _ in range(x):
        v = nodes[v.parent]
    
    snuke = v.v
    fennec = N - snuke
    ans = "Fennec" if fennec > snuke else "Snuke"
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
node=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
visited=[False]*n
def dfs(i):
	dis=[-1]*n
	dis[i]=0
	stack=[i]
	while stack:
		p=stack.pop()
		for x in node[p]:
			if dis[x]==-1:
				dis[x]=dis[p]+1
				stack.append(x)
	return dis
d0,dn=dfs(0),dfs(n-1)
cnt=0
for i in range(n):
	if d0[i]>dn[i]:
		cnt+=1
if cnt>=n/2:
	print("Snuke")
else:
	print("Fennec")

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
distfrom1=[-1]*n
distfromn=[-1]*n
distfrom1[0]=0
distfromn[n-1]=0
d=deque([0])
while d:
    v=d.popleft()
    for i in graph[v]:
        if distfrom1[i]!=-1:continue
        distfrom1[i]=distfrom1[v]+1
        d.append(i)
d.append(n-1)
while d:
    v=d.popleft()
    for i in graph[v]:
        if distfromn[i]!=-1:continue
        distfromn[i]=distfromn[v]+1
        d.append(i)
F=0
for i in range(n):
    if distfrom1[i]<=distfromn[i]:F+=1
if F>n-F:print("Fennec")
else:print("Snuke")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    n = int(input())
    adj_list = [[] for i in range(n)]
    for i in range(n - 1):
        a1, b1 = map(int, sys.stdin.readline().split())
        adj_list[a1 - 1].append(b1 - 1)
        adj_list[b1 - 1].append(a1 - 1)
    path = list(reversed(dfs(0, -1, adj_list, n)))
    assert len(path) >= 2
    fpath = len(path) - len(path) // 2
    cut = set(path[fpath - 1:fpath + 1])
    f = dfs2(0, -1, adj_list, n, cut)
    s = dfs2(n - 1, -1, adj_list, n, cut)
    assert f + s == n
    print("Fennec" if f > s else "Snuke")

def dfs(now, prev, adj_list, n):
    if now == n - 1:
        return [now]
    for next in adj_list[now]:
        if next == prev:
            continue
        p = dfs(next, now, adj_list, n)
        if p is not None:
            p.append(now)
            return p

def dfs2(now, prev, adj_list, n, cut):
    size = 1
    for next in adj_list[now]:
        if next == prev:
            continue
        if {now, next} == cut:
            continue
        s = dfs2(next, now, adj_list, n, cut)
        size += s
    return size

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N=int(input())
G=[[] for i in range(N)]
F=[0 for i in range(N)]
A=[]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
  A.append([a,b])
  
def dfs(s,R):
  F[s]=1
  
  if s==N-1:
    return [s]
  else:
    for n in G[s]:
      if F[n]==0:
        k=dfs(n,R)
        if len(k)!=0:
          k.append(s)
          return k
     
  return []
  
root=dfs(0,[])
#print(root[::-1])
p=root[::-1][len(root)//2+len(root)%2-1]
q=root[::-1][len(root)//2+len(root)%2]

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

    def find(self, 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 = 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):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, 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())

uf = UnionFind(N) 
for i in range(N-1):
  a,b=map(int,A[i])
  if a==p and b==q:
    continue
  if a==q and b==p:
    continue
  uf.union(a, b)

scoreA=uf.size(0)
scoreB=N-scoreA
#print(scoreA,scoreB)

if scoreA>scoreB:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

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

Solution code:
#00:30
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
now = [0]
pre = [10**6 for _ in range(n)]
pst = [[] for _ in range(n)]
seen = [0 for _ in range(n)]
seen[0] = 1
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        pre[y] = x
        pst[x].append(y)
        now.append(y)
#print(pre)
r = 0
z = n-1
while True:
  r += 1
  z = pre[z]
  if z == 0:
    break
z = n-1
for _ in range(r-r//2-1):
  z = pre[z]
cnt = 0
nowz = [z]
#print(z)
while nowz:
  lastz = nowz
  nowz = []
  cnt += len(lastz)
  for x in lastz:
    nowz += pst[x]
  #print(lastz)
if cnt >= (n+1)//2:
  print('Snuke')
else:
  print('Fennec')
#print(cnt)

Submission status: Accepted

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[root] = 1
while stack:
  x = stack.pop()
  if x == n:
    break
  for y in graph[x]:
    if visited[y] == 0:
      stack.append(y)
      visited[y] = visited[x]+1
dist = visited[n]-1
way = n
while True:
  if visited[way] == dist//2+2:
    border = way
    break
  for y in graph[way]:
    if visited[y] == visited[way]-1:
      way = y
stack = [1]
visited = [0 for i in range(n+1)]
visited[border] = 1
fen = 0
while stack:
  x = stack.pop()
  fen += 1
  visited[x] = 1
  for y in graph[x]:
    if visited[y] == 0:
      stack.append(y)
snk = n-fen
if fen > snk:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

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)]

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

Submission status: Accepted

Solution code:
#Snuke vs Fennec
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int, input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
 
 
def dist(n, lis):
    lis[n] = 0
    node = [n]
    while node:
        s = node.pop()
        d = lis[s]
        for t in tree[s]:
            if lis[t] != -1:
                continue
            lis[t] = d + 1
            node.append(t)
    return lis
 
 
from_feneck = dist(0, [-1]*N)
from_Snuke = dist(N-1, [-1]*N)
 
feneck = 0
for i,j in zip(from_feneck, from_Snuke):
    if i<=j:
        feneck += 1
    else:
        feneck -= 1
    
if feneck <= 0:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(1000000)
N = int(input())
graph = {}
SCORE = 0
def dfs(visited,v,depth):
    visited[v] = depth
    for next_v in graph[v]:
        if  visited[next_v]  == -1 :
            dfs(visited,next_v,depth + 1)




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

    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)

vF = [-1] * (N + 1)
vF[1] = 0
dfs(vF,1,0)
# print(vF)

vS = [-1] * (N + 1)
vS[N] = 0

dfs(vS,N,0)
# print(vS)

fc = 0
sc = 0

for f,s in zip(vF[1:N + 1],vS[1:N + 1]):
    if f <= s:
        fc += 1
    else:
        sc += 1

# print(fc,sc)
if fc > sc:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
#分岐は後で処理すれば良い
#それぞれ0,nに近づくのが最適
from heapq import heappush,heappop
inf=10**10
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i
      cost=1
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        heappush(q,[dist[t],t])
  return dist
d1=dijkstra(1)
d2=dijkstra(n)
countp=0
counts=0
for i in range(1,n+1):
  if d1[i]>d2[i]:
    counts+=1
  else:
    countp+=1
if countp>counts:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
#分岐は後で処理すれば良い
#それぞれ0,nに近づくのが最適
import sys
sys.setrecursionlimit(10**8)
from heapq import heappush,heappop
inf=10**10
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
prev=[-1 for i in range(n+1)]
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i
      cost=1
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        prev[t]=v
        heappush(q,[dist[t],t])
  return dist
d=dijkstra(1)
p=[n]
num=n
next=[-1 for i in range(n+1)]
while num!=1:
  num1=prev[num]
  next[num1]=num
  p.append(num1)
  num=num1
countp=[0]
countf=[0]
def dfs(x,y):
  for i in l[x]:#iに分岐可能ならば
    if prev[x]!=i and next[x]!=i:
      if y==1:
        countp[0]+=1
      else:
        countf[0]+=1
      prev[i]=x
      dfs(i,y) 
p=p[::-1]
num=len(p)
num1=(num-1)//2+1
for i in range(num1):
  countp[0]+=1
  dfs(p[i],1)
for i in range(num1,num):
  countf[0]+=1
  dfs(p[i],0)
if countp[0]>countf[0]:
  print("Fennec")
else:
  print("Snuke")