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 deque
n=int(input())
d={}
for i in range(n-1):
    #a,b=map(int,input().split()) ?str spd?
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
    if b in d:
        d[b].append(a)
    else:
        d[b]=[a]
f,s=set([1]),set([n])
e=deque([0,1])
u=deque([0,n])
x=0
while 1:
    if len(e)==len(u)==1: break

    if x%2==0 and len(e)>0:
        while e[-1]!=0:
            tmp=e.pop()
            for i in d[tmp]:
                if i not in f and i not in s:
                    f.add(i)
                    e.appendleft(i)
        e.rotate()
    elif x%2==1 and len(u)>0:
        while u[-1]!=0:
            tmp=u.pop()
            for i in d[tmp]:
                if i not in f and i not in s:
                    s.add(i)
                    u.appendleft(i)
        u.rotate()
    x+=1
print(["Fennec","Snuke"][len(f)<=len(s)])

Submission status: Accepted

Solution code:
n=int(input())
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
pre=[None]*(n+1)
pre[1]=1
q=[1]
while len(q)>0:
    t=q.pop()
    for i in edge[t]:
        if(pre[i]==None):
            pre[i]=t
            q.append(i)
route=[n]
t=n
while t!=1:
    t=pre[t]
    route.append(t)
route=route[::-1]
a=route[(len(route)+1)//2-1]
b=route[(len(route)+1)//2]
edge[a].remove(b)
edge[b].remove(a)
def v(s):
    a=1
    q=[s]
    c=[0]*(n+1)
    c[s]=1
    while len(q)>0:
        t=q.pop()
        for i in edge[t]:
            if(c[i]==0):
                c[i]=1
                a+=1
                q.append(i)
    return a
a=v(a)
b=v(b)
if(a>b):
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    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((1,b-1))
    g[b-1].append((1,a-1))

df = dijkstra(g,N,0)
ds = dijkstra(g,N,N-1)

f = 0
for i in range(N):
    if df[i] <= ds[i]:
        f += 1
if f > N-f:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
from math import ceil

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

N = int(input())
g = Graph()

for _ in range(N-1):
    a,b = map(int,input().split())
    g.add_edge(a,b)
    g.add_edge(b,a)

dij = Dijkstra(g,1)
path = dij.shortest_path(N)
c1 = path[ceil(len(path)/2)-1]
c2 = path[ceil(len(path)/2)]

g.graph[c1] = [(to,cost) for to,cost in g.graph[c1] if to != c2]
g.graph[c2] = [(to,cost) for to,cost in g.graph[c2] if to != c1]

dij = Dijkstra(g,1)
f = 0
for i in range(1,N):
    if dij.shortest_distance(i) != float('inf'):
        f += 1
if f > N-f:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from queue import Queue

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)

q = Queue()
count = [0, 0]
used = [False] * N

q.put((0, 0))
count[0] += 1
used[0] = True

q.put((N - 1, 1))
count[1] += 1
used[N - 1] = True

while not q.empty():
    u, color = q.get()
    for v in g[u]:
        if not used[v]:
            q.put((v, color))
            count[color] += 1
            used[v] = True

print("Fennec" if count[0] > count[1] else "Snuke")

Submission status: Accepted

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


def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num - 1)]
    graph_data = defaultdict(set)
    for i in range(num - 1):
        a, b = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)

    black, white = 0, 0
    b_ind_now, w_ind_now = set(), set()
    b_ind_next, w_ind_next = set(), set()
    # b_ind_pre, w_ind_pre = set(), set()
    pre_ind = set()
    b_ind_now.add(1)
    w_ind_now.add(num)
    # b_ind_pre.add(1)
    # w_ind_pre.add(1)
    pre_ind.add(1)
    pre_ind.add(num)

    while len(b_ind_now) > 0 or len(w_ind_now) > 0:
        for ele_now in b_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                b_ind_next.add(ele_next)
                black += 1
        b_ind_now = b_ind_next
        b_ind_next = set()


        for ele_now in w_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                w_ind_next.add(ele_next)
                white += 1
        w_ind_now = w_ind_next
        w_ind_next = set()

        # print(white, black)

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





if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num - 1)]
    graph_data = defaultdict(set)
    for i in range(num - 1):
        a, b = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)

    black, white = 0, 0
    b_ind_now, w_ind_now = set(), set()
    b_ind_next, w_ind_next = set(), set()
    # b_ind_pre, w_ind_pre = set(), set()
    pre_ind = set()
    b_ind_now.add(1)
    w_ind_now.add(num)
    # b_ind_pre.add(1)
    # w_ind_pre.add(1)
    pre_ind.add(1)
    pre_ind.add(num)

    while len(b_ind_now) > 0 or len(w_ind_now) > 0:
        for ele_now in b_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                b_ind_next.add(ele_next)
                black += 1
        b_ind_now = b_ind_next
        b_ind_next = set()


        for ele_now in w_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                w_ind_next.add(ele_next)
                white += 1
        w_ind_now = w_ind_next
        w_ind_next = set()

        # print(white, black)

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





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    S[a-1].append(b-1)
    S[b-1].append(a-1)
M = [0]*N
M[0],M[N-1] = 1,-1 # 1=黒=フェネック
F_que = S[0]
S_que = S[-1]
while F_que != S_que:
    n_que = []
    for i in F_que:
        if M[i] == 0:
            M[i] = 1
            for j in S[i]:
                n_que.append(j)
    F_que = n_que
    n_que = []
    for i in S_que:
        if M[i] == 0:
            M[i] = -1
            for j in S[i]:
                n_que.append(j)
    S_que = n_que
print(["Snuke","Fennec"][sum(M) > 0])

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
stack1=deque(G[0])
stack2=deque(G[N-1])
X=[-1]*N
X[0]=1
X[N-1]=0
while(stack1 or stack2):
    Stack1=deque()
    for i in stack1:
        if X[i]==-1:
            X[i]=1
            for j in G[i]:
                if X[j]==-1:
                    Stack1.append(j)
    stack1=Stack1
    Stack2=deque()
    for i in stack2:
        if X[i]==-1:
            X[i]=0
            for j in G[i]:
                if X[j]==-1:
                    Stack2.append(j)
    stack2=Stack2
f,s=0,0
for i in range(N):
    if X[i]==1:
        f+=1
    else:
        s+=1
if f>s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def dfs(idx, cur, conn, dis):
        dis[idx] = cur
        for nex in conn[idx]:
            if dis[nex] is None:
                dfs(nex, cur + 1, conn, dis)
        return None

    f_dis = [None] * N
    f_dis[0] = 0
    dfs(0, 0, conn, f_dis)

    s_dis = [None] * N
    s_dis[N - 1] = 0
    dfs(N - 1, 0, conn, s_dis)

    cnt = 0
    for i in range(N):
        if f_dis[i] <= s_dis[i]:
            cnt += 1

    if cnt > (N - cnt):
        ret = 'Fennec'
    else:
        ret = 'Snuke'
    print(ret)
    return


def _solve(N: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def find_path(idx, target, conn, visited):
        visited[idx] = True
        if idx == target:
            return [target]
        for nex in conn[idx]:
            if not visited[nex]:
                path = find_path(nex, target, conn, visited)
                if path is not None:
                    return [idx] + path
        return None

    visited = [False] * N
    path_to_n = find_path(0, N - 1, conn, visited)
    #print(path_to_n)

    colors = [None] * N
    for i, node in enumerate(path_to_n):
        if i < (len(path_to_n) + 1) // 2:
            colors[node] = 1
        else:
            colors[node] = 0

    def dfs(idx, conn, colors, visited):
        visited[idx] = True
        colors[idx] = 1
        for nex in conn[idx]:
            if not visited[nex] and (colors[nex] is None or colors[nex] == 1):
                dfs(nex, conn, colors, visited)
        return

    visited = [False] * N
    dfs(0, conn, colors, visited)
    #print(colors)

    cnt = 0
    for c in colors:
        if c == 1:
            cnt += 1
    if cnt > (N - cnt):
        ret = 'Fennec'
    else:
        ret = 'Snuke'
    print(ret)
    return


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))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def dfs(idx, cur, conn, dis):
        dis[idx] = cur
        for nex in conn[idx]:
            if dis[nex] is None:
                dfs(nex, cur + 1, conn, dis)
        return None

    f_dis = [None] * N
    f_dis[0] = 0
    dfs(0, 0, conn, f_dis)

    s_dis = [None] * N
    s_dis[N - 1] = 0
    dfs(N - 1, 0, conn, s_dis)

    cnt = 0
    for i in range(N):
        if f_dis[i] <= s_dis[i]:
            cnt += 1

    if cnt > (N - cnt):
        ret = 'Fennec'
    else:
        ret = 'Snuke'
    print(ret)
    return


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))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = MI_()
        edge[a].append(b)
        edge[b].append(a)

    set_A = set()
    set_B = set()
    a_stack = [0]
    b_stack = [N - 1]
    for _ in range(N - 1):
        tmp_a = []
        tmp_b = []
        while a_stack:
            from_ = a_stack.pop()
            for to in edge[from_]:
                if to not in set_A and to not in set_B:
                    tmp_a.append(to)
                    set_A.add(to)
        while b_stack:
            from_ = b_stack.pop()
            for to in edge[from_]:
                if to not in set_A and to not in set_B:
                    tmp_b.append(to)
                    set_B.add(to)
        a_stack = tmp_a
        b_stack = tmp_b
    if len(set_A) > len(set_B):
        print("Fennec")
    else:
        print("Snuke")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

import numpy as np

sys.setrecursionlimit(2 ** 31 - 1)
INF = float('inf')

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]

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

s1 = [1]
s2 = [N]
fennec = 0
snuke = 0
fixed = np.zeros(N + 1, dtype=bool)
while s1 or s2:
    u1 = []
    for v in s1:
        if fixed[v]:
            continue
        fixed[v] = True
        fennec += 1
        u1.extend(graph[v])
    s1 = u1

    u2 = []
    for v in s2:
        if fixed[v]:
            continue
        fixed[v] = True
        snuke += 1
        u2.extend(graph[v])
    s2 = u2

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
Edges=[]
for i in range(n-1):
  a,b=map(int,input().split())
  Edges.append([a,b,1])
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
F,S=BFS(0,Edges,n),BFS(n-1,Edges,n)
count=0
for i in range(1,n-1):
  if F[i]<=S[i]:
    count+=1
  else:
    count-=1
print("Fennec" if count>0 and n!=2 else "Snuke")

Submission status: Accepted

Solution code:
class Union():
  def __init__(me,N):
    me.N = N
    me.up = [-1]*N
    me.down = [ [] for i in range(N) ]
  def union(me,a,b):
    ua = me.up[a] if me.up[a]!=-1 else a
    ub = me.up[b] if me.up[b]!=-1 else b
    if (ua == ub):
      return
    if ( len(me.down[ua]) < len(me.down[ub]) ):
      ub,ua = ua,ub
    for v in me.down[ub]:
      me.up[v] = ua
    me.down[ua].extend( me.down[ub] )
    me.down[ub] = []
    me.up[ub] = ua
    me.down[ua].append( ub )
  def count(me,a):
    ua = me.up[a] if me.up[a]!=-1 else a
    return len(me.down[ua])+1

N = int(input())

li = [ [ int(it) -1 for it in input().split() ] for i in range(N-1) ]

down = [ [] for i in range(N) ]

for a,b in li:
  down[a].append(b)
  down[b].append(a)

mita = [0]*N
mita[0]=1
kouho = [0]
dist = [100000000000000000]*N
dist[0] = 0

for i in range(10000000000000000):
  if ( len(kouho) == 0 ):
    break
  n = kouho.pop()
  for k in down[n]:
    if ( mita[k] == 0 ):
      dist[k] = min(dist[k],dist[n]+1)
      mita[k] = 1
      kouho.append(k)

route = [N-1]
for i in range(10000000000000000):
  n = route[-1]
  if ( n == 0 ):
    break
  s = 100000000000000
  sk = -1
  for k in down[n]:
    if (s > dist[k] - dist[n]):
      s = dist[k] - dist[n]
      sk = k
  route.append(sk)   
route.reverse()
x,y = route[ (len(route)-1)//2 ],route[ 1+((len(route)-1)//2) ]

u = Union(N)
for a,b in li:
  if (a==x and b==y) or (a==y and b==x):
      continue
  u.union(a,b)

if ( u.count(0) <= u.count(N-1) ):
  print ( "Snuke" )
else:
  print ( "Fennec" )

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(114514)
N=int(input())
path=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b=map(int,input().split())
	path[a].append(b)
	path[b].append(a)
fenne=[-1 for _ in range(N+1)]
snuke=[-1 for _ in range(N+1)]
def walk(ar, i, d):
	if ar[i] == -1:
		ar[i] = d
		for x in path[i]:
			walk(ar, x, d+1)
walk(fenne, 1, 0)
walk(snuke, N, 0)
f,s=0,0
for i in range(1, N+1):
	if snuke[i] < fenne[i]:
		s+=1
	else:
		f+=1


print("Fennec" if f > s else "Snuke")

Submission status: Accepted

Solution code:
N=int(input())
E=[[] for _ in [0]*N]
for _ in [0]*(N-1):
    a,b=map(int,input().split())
    E[a-1]+=[b-1]
    E[b-1]+=[a-1]
V=[1]+[0]*(N-2)+[-1]
q=[0,N-1]
while q:
    p=[]
    for i in q:
        for j in E[i]:
            if not V[j]:
                V[j]=V[i]
                p+=[j]
    q=p
print("Fennec" if sum(V)>0 else "Snuke")

Submission status: Accepted

Solution code:
N = int(input())
E = [[] for _ in [0]*N]
for _ in [0]*(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
V = [0]*N
V[0] = 1
V[-1] = -1
q = [0,N-1]
while q:
    qq = []
    for i in q:
        Vi = V[i]
        for j in E[i]:
            if not V[j]:
                V[j] = Vi
                qq.append(j)
    q = qq
print("Fennec" if sum(V)>0 else "Snuke")

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]

adja_dict={}

for a,b in AB:
  adja_dict.setdefault(a, set()).add(b)
  adja_dict.setdefault(b, set()).add(a)

nodes = [None] * (N+2) #N[0]:b N[N+1]:w
nodes[0] = nodes[1] = 1
nodes[N] = nodes[N+1] = -1

from collections import deque
dq = deque([1, N])
while dq:
  x = dq.popleft()
  for y in adja_dict[x]:
    if nodes[y] is None:
      nodes[y] = nodes[x]
      dq.append(y)
#print(nodes)
if sum(nodes)>0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
# 木グラフなので各プレイヤから近い点の個数を比べればよい

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)  

INF = 10**18

d_fe = [INF]*N
d_sn = [INF]*N

d_fe[0] = 0
d_sn[N-1] = 0

def f(d,x):
  dx = d[x]
  for v in edge[x]:
    if d[v] == INF:
      d[v] = dx+1
      f(d,v)
      
f(d_fe,0)
f(d_sn,N-1)

black = 0
white = 0

for x in range(N):
  if d_fe[x] <= d_sn[x]:
    black += 1
  else:
    white += 1

answer = 'Fennec' if black > white else 'Snuke'
print(answer)

Submission status: Accepted

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

N = int(readline())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    s,t = map(lambda x:int(x)-1, readline().split())
    edges[s].append(t)
    edges[t].append(s)

def bfs(edges, s)->list:
    V = len(edges)
    dist = [float('inf')]*V
    visited = [False]*V
    dist[s] = 0
    visited[s] = True
    q = deque([s])
    while q:
        cur = q.popleft()
        for nex in edges[cur]:
            if visited[nex]:
                continue
            q.append(nex)
            visited[nex] = True
            dist[nex] = dist[cur] + 1
    return dist

dist1 = bfs(edges, 0)
dist2 = bfs(edges, N-1)
score1 = 0
for d1,d2 in zip(dist1, dist2):
    if d1 <= d2:
        score1 += 1
# print(score1)
print("Fennec" if score1 > N/2 else "Snuke")

Submission status: Accepted

Solution code:
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    s,t = map(lambda x:int(x)-1, input().split())
    edges[s].append(t)
    edges[t].append(s)

from collections import deque
def bfs(edges, s)->list:
    V = len(edges)
    dist = [float('inf')]*V
    visited = [False]*V
    dist[s] = 0
    visited[s] = True
    q = deque([s])
    while q:
        cur = q.popleft()
        for nex in edges[cur]:
            if visited[nex]:
                continue
            q.append(nex)
            visited[nex] = True
            dist[nex] = dist[cur] + 1
    return dist

dist1 = bfs(edges, 0)
dist2 = bfs(edges, N-1)
score1 = 0
for d1,d2 in zip(dist1, dist2):
    if d1 <= d2:
        score1 += 1
# print(score1)
print("Fennec" if score1 > N/2 else "Snuke")

Submission status: Accepted

Solution code:
import queue 

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)

f = [0]*N
vf = [False] * N
qf = queue.Queue()
qf.put(0)
vf[0] = True

while not qf.empty():
    now = qf.get()
    edge = len(graph[now])
    if not edge == 0:
        for i in range(edge):
            if not vf[graph[now][i]]:
                qf.put(graph[now][i])
                f[graph[now][i]] = f[now]+1
                vf[graph[now][i]] = True

s = [0]*N
vs = [False] * N
qs = queue.Queue()
qs.put(N-1)
vs[N-1] = True

while not qs.empty():
    now = qs.get()
    edge = len(graph[now])
    if not edge == 0:
        for i in range(edge):
            if not vs[graph[now][i]]:
                qs.put(graph[now][i])
                s[graph[now][i]] = s[now]+1
                vs[graph[now][i]] = True

score = 0
for i in range(N):
    if f[i] <= s[i]:
        score += 1
    else:
        score -= 1

if score > 0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from functools import reduce
import math
from collections import deque
from collections import defaultdict

def bfs(i,d,N):
    q = deque()
    q.append(i)
    d_from_1 = [-1]*(N+1)
    d_from_1[i] = 0
    i = 1
    while q:
        l = len(q)
        for j in range(l):
            next_node = q.popleft()
            for succ in d[next_node]:
                if d_from_1[succ] == -1:
                    d_from_1[succ] = i
                    q.append(succ)
        i += 1
    return d_from_1
    
def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)       
    f= 0
    s= 0
    d_from_1 = bfs(1,d,N)
    d_from_N = bfs(N,d,N)
        
    # print(d_from_1)
    # print(d_from_N)
    for i in range(1,N+1):
        if(d_from_1[i] <= d_from_N[i]):
            f += 1
        else:
            s += 1
    if(f>s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
import math
from collections import deque
from collections import defaultdict

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)
        
    bw = defaultdict(str)
    bw[1] = 'b'
    bw[N] = 'w'
    f= 0
    s= 0
    q = deque()
    q.append(1)
    q.append(N)
    while q:
        next_node = q.popleft()
        if(bw[next_node] == 'b'):
            f+=1
        elif(bw[next_node] == 'w'):
            s+=1
        for succ in d[next_node]:
            if bw[succ] == '':
                bw[succ] = bw[next_node]
                q.append(succ)
    if(f>s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()

Submission status: Accepted

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


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in T[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


Black = dijkstra(0)
White = dijkstra(N - 1)

Black_point = 0
for b, w in zip(Black, White):
    if b <= w:
        Black_point += 1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N=input()

nl=[ [] for i in range(N+1)]
D=[ 0 for i in range(N+1)]	# No.1からの距離
V=[ 0 for i in range(N+1)]	# 訪問済みフラグ

for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	nl[b].append(a)


def bfs(v):	#1からの頂点Nまでの距離を算出
	q = deque([]) 
	V[v]=1
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if V[i]==0:
				D[i]=D[v]+1
				V[i]=1
				q.append(i)

bfs(1)


L=deque([]) 	#1-Nまでの最短経路を復元 
def bfs2(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if D[i]==D[v]-1 and i!=1:
				q.append(i)
				L.appendleft(i)

bfs2(N)


color=[ None for i in range(N+1)]
color[1]="b"
color[N]="w"

l=len(L)
for i in range( (l+1)/2 ):
	color[ L[i] ]="b"

for i in range( (l+1)/2, l ):
	color[ L[i] ]="w"


def bfs3(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if color[i] is None:
				color[i]=color[v]
				q.append(i)

L.append(1)
L.append(N)
for i in L:
	bfs3(i)
		

b_cnt=color.count("b")
w_cnt=color.count("w")


if N%2==1:
	if b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"
else:
	if b_cnt==w_cnt:	
		print "Snuke"
	elif b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"

Submission status: Accepted

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

B = [False]*N
visited = [True]*N

Fp,Sp = 0,0
Fi,Si = [0],[N-1]

while B != visited:
    # Fennec
    nextXi = []
    for i in Fi:
        if not B[i]:
            B[i] = True
            Fp += 1
            nextXi.extend(A[i])
    Fi = nextXi
    # Snuke
    nextXi = []
    for i in Si:
        if not B[i]:
            B[i] = True
            Sp += 1
            nextXi.extend(A[i])
    Si = nextXi

print("Fennec" if Fp>Sp else "Snuke")