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:
n = int(input())
edges = [[] for _ in range(n)]

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

def bfs(v):
    q = []
    depth = [n]*n
    q.append(v)
    depth[v] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth

d1 = bfs(0)
d2 = bfs(n-1)

c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
def dfs(x):
	d,q = [-1 for i in range(n+1)],[x]
	d[x] = 0
	while q:
		x = q.pop()
		for i in r[x]:
			if d[i]==-1: d[i],q = d[x]+1,q+[i]
	return d
n = int(input())
x = [[int(i) for i in input().split()] for i in range(n-1)]
r = [[] for i in range(n+1)]
for i,j in x:
	r[i].append(j)
	r[j].append(i)
d1,dn,num = dfs(1),dfs(n),0
for i in range(1,n+1):
	if d1[i]<=dn[i]: num+=1
if num>n//2: print("Fennec")
else: print("Snuke")

Submission status: Accepted

Solution code:
N = int(input())
eda = {}
for i in range(1, N+1):
    eda[i] = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    eda[a].add(b)
    eda[b].add(a)
fennec = 0
snuke = 0
fenneccheck = set([1])
snukecheck = set([N])
checked = set([1, N])
while len(checked) < N:
    nextfennec = set()
    for i in fenneccheck:
        for j in eda[i]:
            if j in checked:
                continue
            checked.add(j)
            nextfennec.add(j)
            fennec += 1
    fenneccheck = nextfennec
    nextsnuke = set()
    for i in snukecheck:
        for j in eda[i]:
            if j in checked:
                continue
            checked.add(j)
            nextsnuke.add(j)
            snuke += 1
    snukecheck = nextsnuke
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
N = int(input())
ab = [[int(_) for _ in input().split()] for n in range(N - 1)]

from collections import defaultdict

ns = defaultdict(list)

for a, b in ab:
    ns[a].append(b)
    ns[b].append(a)

from heapq import *

queue = []
heappush(queue, (0, 1))
heappush(queue, (1, N))

colors = defaultdict(lambda:None)
black_count, white_count = 0, 0

while queue:
    i, index = heappop(queue)
    color = i % 2
    if colors[index] is None:
        colors[index] = color
        if color:
            white_count += 1
        else:
            black_count += 1
        for t in ns[index]:
            if ns[t]:
                heappush(queue, (i + 2, t))

if black_count > white_count:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
N = int(input())
ab = [[int(_) for _ in input().split()] for n in range(N - 1)]

ns = [[] for _ in range(N + 1)]

for a, b in ab:
    ns[a].append(b)
    ns[b].append(a)

from heapq import *

queue = []
heappush(queue, (0, 1))
heappush(queue, (1, N))

counts = [0, 0]

while queue:
    i, index = heappop(queue)
    if ns[index]:
        counts[i % 2] += 1
        for t in ns[index]:
            if ns[t]:
                heappush(queue, (i + 2, t))
    ns[index] = None

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N=int(input())
M=defaultdict(list)

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

def bfs(s):
  res=[-1 for x in range(N)]
  res[s]=0
  queue=[s]
  while queue:
    np=queue.pop()
    for nx in M[np]:
      if res[nx]<0:
        res[nx]=res[np]+1
        queue.append(nx)
  return res

ans0=bfs(0)
ansN=bfs(N-1)
cnt=0
for i in range(N):
  if ans0[i]<=ansN[i]:
    cnt+=1
if cnt > N/2:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''
深さ優先探索で解く
木構造で解く
'''


n = int(input())
a=[[] for i in range(n)]
for i in range(n-1):
    b=[int(j)-1 for j in input().split()]
    a[b[0]].append(b[1])
    a[b[1]].append(b[0])

def dfs(v):
    d=[-1 for i in range(n)]
    q=[]
    d[v]=0
    q.append(v)
    while len(q):
        v=q.pop()

        for i in a[v]:
            if d[i]==-1:
                d[i]=d[v]+1
                q.append(i)
    return d
c1=dfs(0)
c2=dfs(n-1)
c=0
for i in range(n):
    if c1[i]>c2[i]:
        c+=1
if c>=n/2:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return tuple(map(int, input().split()))

N = int(input())
G = [[] for i in range(N+1)]
for _ in range(N-1):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)

F = ["" for i in range(N+1)]
S = ["" for i in range(N+1)]

visited = [False for i in range(N+1)]
Q = deque([(1, 0)])

while len(Q):
    m, d = Q.popleft()
    if visited[m]:
        continue
    else:
        F[m] = d
        visited[m] = True

    for nm in G[m]:
        Q.append((nm, d+1))

visited = [False for i in range(N+1)]
Q = deque([(N, 0)])

while len(Q):
    m, d = Q.popleft()
    if visited[m]:
        continue
    else:
        S[m] = d
        visited[m] = True

    for nm in G[m]:
        Q.append((nm, d+1))
    
black = 0    
for i in range(1, N+1):
    if F[i] <= S[i]:
        black += 1

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

Submission status: Accepted

Solution code:
def bfs(n, links):
    painted = set()
    queues = [{0}, {n - 1}]
    scores = [0, 0]
    i = 0
    while True:
        nq = set()
        for v in queues[i]:
            cq = links[v] - painted
            if cq:
                painted.update(cq)
                nq.update(cq)
        queues[i] = nq
        scores[i] += len(nq)
        if not nq:
            scores[i ^ 1] = n - scores[i]
            break
        i ^= 1
    return scores[0] > scores[1]


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('Fennec' if bfs(n, links) else 'Snuke')

Submission status: Accepted

Solution code:
def bfs(n, links):
    painted = set()
    fq = {0}
    sq = {n - 1}
    fs, ss = 0, 0
    while True:
        nfq, nsq = set(), set()
        for v in fq:
            cfq = links[v] - painted
            if cfq:
                fs += len(cfq)
                painted.update(cfq)
                nfq.update(cfq)
        fq = nfq
        for v in sq:
            csq = links[v] - painted
            if csq:
                ss += len(csq)
                painted.update(csq)
                nsq.update(csq)
        sq = nsq
        if not fq:
            ss = n - fs
            break
        if not sq:
            fs = n - ss
            break
    return fs > ss


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('Fennec' if bfs(n, links) else 'Snuke')

Submission status: Accepted

Solution code:
n = int(input())
node = [[] for i in range(n)]

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

def dfs(v):
    dis = [10 ** 10] * n
    dis[v] = 0
    q = []
    q.append(v)

    while q:
        u = q.pop()
        for i in node[u]:
            if dis[i] > dis[u] + 1:
                dis[i] = dis[u] + 1
                q.append(i)

    return dis

d1 = dfs(0)
d2 = dfs(n - 1)

c = 0
for i in range(1, n - 1):
    if d1[i] <= d2[i]:
        c += 1

if c > (n - 2) // 2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());n,=f();a,b=zip(*map(f,[0]*~-n));g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,(a,b)),[n+1]*2),0,[1,n]);print['Snuke','Fennec'][sum(g[i]>h[i]for i in range(n+1))*2<n]

Submission status: Accepted

Solution code:

from collections import Counter

N = int(input())
graph =[[] for _ in range(N + 1)]
visited = [None] * (N + 1)

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

v = 1
adv_v = N
update = True
labels = [0, 1]
vs = [v, adv_v]
prev_vs = [-1, -1]
visited[1] = 0
visited[N] = 1
while update:
    update = False
    next_cand = []

    for label, v, prev_v in zip(labels, vs, prev_vs):
        for next_v in graph[v]:
            if next_v == prev_v:
                continue
            if (visited[next_v] is None):
                update = True
                next_cand.append((next_v, label, v))

    vs = []
    labels = []
    prev_vs = []
    for next_v, label, prev_v in next_cand:
        if visited[next_v] is None:
            visited[next_v] = label
            vs.append(next_v)
            prev_vs.append(prev_v)
            labels.append(label)


c = Counter(visited)
if c[0] > c[1]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))
 
import copy
 
N = ri()
relation = [[] for _ in range(N+1)]
dist = [[0 for i in range(N+1)] for j in range(2)]
for i in range(N-1):
    a,b = rli()
    relation[a].append(b)
    relation[b].append(a)
 
def dfs_visit(u):
    start = u
    rel = copy.deepcopy(relation)
    s = []
    color = [-1 for _ in range(N+1)]
    s.append(u)
    color[u] = 0
    while(s != list()):
        u = s[-1]
        try:
            v = rel[u].pop()
        except IndexError:
            dist[0 if start == 1 else 1][s[-1]] = len(s)
            s.pop()
            color[u] = 1
            continue
        if(color[v] == -1):
            color[v] = 0
            s.append(v)
 
def dfs():
    dfs_visit(1)
    dfs_visit(N)
 
dfs()
fe = 0
sn = 0
 
for i in range(1, N+1):
    if(dist[0][i] <= dist[1][i]):
        fe += 1
    else:
        sn += 1
print("Fennec" if fe > sn else "Snuke")

Submission status: Accepted

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 = set(pass_route)
        self.pass_route.add(now_number)

    def set_now_number(self, now_number):
        self.now_number = now_number
        self.pass_route.add(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
    node_list = [1]
    count = 0
    while 1:
        #count += 1
        #print count
        #new_node_list = []
        m_node = node_list[len(node_list) - 1]
        is_already_pass[m_node - 1] = True
        is_leaf_node = True
        if m_node == N:
            break;
        for next_node in adj_list[m_node]:
            if is_already_pass[next_node - 1] == False:
                is_leaf_node = False
                node_list.append(next_node)
        if is_leaf_node == True:
            node_list.pop()
        if len(node_list) == 0:
            break;

    to_N_pass_route = deque([])
    for i in range(len(node_list)):
        if is_already_pass[node_list[i] - 1] == True:
            to_N_pass_route.append(node_list[i])


    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)

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

Solution code:
def black(now):
    nextb=[]
    while now:
        a=now.pop()
        while desn[a]:
            go=desn[a].pop()
            if nodes[go]=='N':
                nodes[go]='B'
                nextb.append(go)
    return nextb

def white(now):
    nextb=[]
    while now:
        a=now.pop()
        while desn[a]:
            go=desn[a].pop()
            if nodes[go]=='N':
                nodes[go]='W'
                nextb.append(go)
    return nextb

n = int(input())
nodes=[]
desn=[]
for i in range(0,n+1):
    nodes.append("N")
    desn.append([])
nodes[1]='B'
nodes[n]='W'
for i in range(0,n-1):
    b, c = (int(i) for i in input().split())
    desn[b].append(c)
    desn[c].append(b)

nowb=[1]
noww=[n]
while nowb or noww:
    nowb=black(nowb)
    noww=white(noww)

b=nodes.count('B')
w=nodes.count('W')
if b>w:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
N=int(input())
graph=[[] for i in range(N)]
for _ in range(N-1):
    a,b=list(map(int,input().strip().split(' ')))
    graph[a-1]+=[b-1]
    graph[b-1]+=[a-1]
from collections import deque
def bfs(graph):
    q=deque([0])
    N=len(graph)
    visit=[]
    parent=[-1]*N
    while(q):
        v=q.popleft()
        visit+=[v]
        for adj in  graph[v]:
            if adj!=parent[v]:
                parent[adj]=v
                q+=[adj]
    return visit,parent
visit,parent=bfs(graph)
path=[]
v=N-1
path+=[v]
while(parent[v]!=-1):
    v=parent[v]
    path+=[v]
subtree=[0 for i in range(N)]
for i in range(1,len(visit)+1):
    v=visit[-i]
    if graph[v]==[parent[v]]:
        subtree[v]=1
    else:
        temp=0
        for adj in graph[v]:
            if adj!=parent[v]:
                temp+=subtree[adj]
        subtree[v]=temp+1
ca1=0
ca2=0
if len(path)%2==0:
    stop=(len(path))//2-1
    stop=path[stop]
    ca2=subtree[stop]
    ca1=N-ca2

    if ca1>=ca2+1:
        print('Fennec')
    else:
        print('Snuke')
else:
    stop=(len(path))//2-1
    stop=path[stop]
    
    ca2=subtree[stop]
    ca1=N-ca2
    
    if ca1>=ca2+1:
        print('Fennec')
    else:
        print('Snuke')

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b = LI()
        e[a].append(b)
        e[b].append(a)

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv in e[u]:
                ud = 1
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    ad = search(1)
    bd = search(n)
    t = -1
    for i in range(2,n):
        if ad[i] <= bd[i]:
            t += 1
        else:
            t -= 1

    if t >= 0:
        return 'Fennec'

    return 'Snuke'


print(main())

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());n,=f();a,b=zip(*map(f,[0]*~-n));g,h=[csgraph.dijkstra(csr_matrix(([1]*~-n,(a,b)),[n+1]*2),0,s)for s in[1,n]];print['Snuke','Fennec'][sum(g[i]>h[i]for i in range(n+1))*2<n]

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());d=lambda s:csgraph.dijkstra(csr_matrix(([1]*len(a),(a,b)),[n+1]*2),0,s);n,=f();a,b=zip(*map(f,[0]*~-n));g=d(1);h=d(n);print['Snuke','Fennec'][sum(g[i]>h[i]for i in range(n+1))*2<n]

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());d=lambda s:csgraph.dijkstra(csr_matrix(([1]*len(a),(a,b)),[n+1]*2),0,s);n,=f();a,b=zip(*map(f,[0]*~-n));g=d(1);h=d(n);print['Snuke','Fennec'][sum(g[i]>h[i] for i in range(n+1))*2<n]

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());d=lambda s:csgraph.dijkstra(csr_matrix(([1]*len(a),(a,b)),[n+1]*2),0,s);n,=f();a,b=zip(*map(f,[0]*~-n));g=d(1);h=d(n);print'Fennec'if sum(g[i]>h[i] for i in range(n+1))*2<n else'Snuke'

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=lambda*z:map(int,raw_input().split())
d=lambda s:csgraph.dijkstra(csr_matrix(([1]*len(a),(a,b)),[n+1]*2),0,s)
n,=f()
a,b=zip(*map(f,[0]*~-n))
g=d(1)
h=d(n)
print 'Fennec'if sum(g[i]>h[i] for i in range(n+1))*2<n else'Snuke'

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=lambda*z:map(int,raw_input().split())
d=lambda s:csgraph.dijkstra(csr_matrix(([1]*len(a),(a,b)),[n+1]*2),0,s)
n,=f()
a,b=zip(*map(f,[0]*~-n))
g=d(1)
h=d(n)
print 'Snuke'if sum(g[i]>h[i] for i in range(n+1))*2>=n else'Fennec'

Submission status: Accepted

Solution code:
from collections import*
n=input();G=[[]for d in[deque([1,n])]*-~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]:
  if C[t]<1:C[t]=C[v];d+=t,
print["Snuke","Fennec"][n<2*C.count(1)]

Submission status: Accepted

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]:
  if C[t]<1:C[t]=C[v];d+=t,
print["Fennec","Snuke"][2*C.count(1)<=n]

Submission status: Accepted

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))

import copy

N = ri()
relation = [[] for _ in range(N+1)]
dist = [[0 for i in range(N+1)] for j in range(2)]
for i in range(N-1):
    a,b = rli()
    relation[a].append(b)
    relation[b].append(a)

def dfs_visit(u):
    start = u
    rel = copy.deepcopy(relation)
    s = []
    color = [-1 for _ in range(N+1)]
    s.append(u)
    color[u] = 0
    while(s != list()):
        u = s[-1]
        try:
            v = rel[u].pop()
        except IndexError:
            dist[0 if start == 1 else 1][s[-1]] = len(s)
            s.pop()
            color[u] = 1
            continue
        if(color[v] == -1):
            color[v] = 0
            s.append(v)
 
def dfs():
    dfs_visit(1)
    dfs_visit(N)

dfs()
fe = 0
sn = 0

for i in range(1, N+1):
    if(dist[0][i] <= dist[1][i]):
        fe += 1
    else:
        sn += 1
print("Fennec" if fe > sn else "Snuke")

Submission status: Accepted

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

def bfs(_s):
    q = queue.Queue()
    global d
    d = [float("inf") for i in range(N)]
    used = [False for i in range(N)]
    used[_s] = True
    d[_s] = 0
    q.put(_s)

    while not q.empty():
        p = q.get()
        for i in range(0, len(G[p])):
            if not used[G[p][i]]:
                used[G[p][i]] = True
                d[G[p][i]] = d[p] + 1
                q.put(G[p][i])


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))
        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    # Fennec
    global d
    bfs(0)
    Fennec_d = d

    # sunuke
    bfs(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: Accepted

Solution code:

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist



N=int(input())

g=myGraph()
for i in range(N-1):
    a,b=list(map(int,input().split(" ")))
    g.add_edge([a,b],1)

b1=g.dijkstra(1)
b2=g.dijkstra(N)

count=0
for k in range(1,N+1):
    if b1[k]<=b2[k]:
        count+=1

if count>N/2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
def read_data():
    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)
    return N, Es

def solve(N, Es):
    if N == 2:
        return "Snuke"
    visited = [0] * N
    f1 = [0]
    fN = [N - 1]
    visited[0] = 1
    visited[N - 1] = -1
    while (f1 or fN):
        new_f1 = []
        for v in f1:
            for u in Es[v]:
                if visited[u]: continue
                visited[u] = 1
                new_f1.append(u)
        f1 = new_f1
        new_fN = []
        for v in fN:
            for u in Es[v]:
                if visited[u]: continue
                visited[u] = -1
                new_fN.append(u)
        fN = new_fN
    if sum(visited) > 0:
        return "Fennec"
    else:
        return "Snuke"

N, Es = read_data()
print(solve(N, Es))

Submission status: Accepted

Solution code:
n=int(input())
a=[[] for i in range(n)]
for i in range(n-1):
  b=[int(j)-1 for j in input().split()]
  a[b[0]].append(b[1])
  a[b[1]].append(b[0])

def dfs(v):
    d=[-1 for i in range(n)]
    q=[]
    d[v]=0
    q.append(v)
    while len(q):
        v=q.pop()
           
        for i in a[v]:
            if d[i]==-1:
                d[i]=d[v]+1
                q.append(i)
    return d
c1=dfs(0)
c2=dfs(n-1)
c=0
for i in range(n):
 if c1[i]>c2[i]:
    c+=1
if c>=n/2:
  print("Snuke")
else:
  print("Fennec")

Submission status: Accepted

Solution code:
N=int(raw_input())
tree=[]
for i in range(N):
    tree.append([])
for i in range(N-1):
    inp=map(int,raw_input().split())
    tree[inp[0]-1].append(inp[1]-1)
    tree[inp[1]-1].append(inp[0]-1)
nodes=[1]+[0]*(N-1)
route=[0]
node=0
while 1:
    flag=True
    for i in tree[node]:
        if nodes[i]==0:
            nodes[i]=1
            route.append(i)
            node=i
            flag=False
            break
    if flag:
        route.pop()
        node=route[-1]
    if node==N-1:
        break
l=len(route)
nodes=[0]*N
for i in range((len(route)+1)/2,len(route)):
    nodes[route[i]]=1
total=0
node=0
route.append(0)
while len(route)>l:
    flag=True
    for i in tree[node]:
        if nodes[i]==0:
            total+=1
            nodes[i]=1
            route.append(i)
            node=i
            flag=False
            break
    if flag:
        route.pop()
        node=route[-1]
if total*2>N:
    print "Fennec"
else:
    print "Snuke"