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

Solution (Python):
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')

Solution (Python):
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())

Solution (Python):
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]

Solution (Python):
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]

Solution (Python):
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]

Solution (Python):
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'

Solution (Python):
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'

Solution (Python):
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'

Solution (Python):
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)]

Solution (Python):
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]

Solution (Python):
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")

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

    
    global d
    bfs(0)
    Fennec_d = d

    
    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

    
    

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

Solution (Python):

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] = {}

        
        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 = {k:float('inf') for k in self.nodes}
        

        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:
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    

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

Solution (Python):
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))

Solution (Python):
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")

Solution (Python):
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"

Solution (Python):

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"
    path = find_path(N, 0, N - 1, Es)
    len_path = len(path)
    a = (len_path - 1)// 2
    b = a + 1
    p1 = path[a]
    p2 = path[b]
    e1 = count_edges(N, p1, p2, Es)
    e2 = N - e1
    if e1 > e2:
        return "Fennec"
    else:
        return "Snuke"

def find_path(N, s, g, Es):
    stack = [(s, 0)]
    path = []
    visited = [False] * N
    visited[s] = True
    while True:
        v, d = stack[-1]
        if (path and path[-1][0] == v):
            stack.pop()
            path.pop()
            continue
        if (path and path[-1][1] >= d):
            path.pop()
        path.append((v, d))
        for u in Es[v]:
            if visited[u]:
                continue
            stack.append((u, d + 1))
            visited[u] = True;
            if u == g:
                path = [p for p, depth in path] + [g]
                return path

def count_edges(N, p1, p2, Es):
    stack = [p1]
    visited = [False] * N
    visited[p1] = True
    visited[p2] = True
    count = 0
    while stack:
        v = stack.pop()
        count += 1
        for u in Es[v]:
            if visited[u]:
                continue
            stack.append(u)
            visited[u] = True
    return count


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

Solution (Python):

import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    edges = collections.defaultdict(list)
    for __ in range(N - 1):
        a, b = ILI()
        edges[a].append(b)
        edges[b].append(a)
    return N, edges


def solve(N, edges):
    queue_from_f = set()
    queue_from_s = set()
    queue_from_f.add(1)
    queue_from_s.add(N)

    n_node_f = 1
    snuke_bool = True

    visited_f = [False] * (N + 1)
    visited_s = [False] * (N + 1)
    visited_f[0], visited_f[1] = True, True
    visited_s[0], visited_s[N] = True, True

    while len(queue_from_f) != 0:
        f_next_queue = set()
        for i in queue_from_f:
            next_point = edges[i]
            for point in next_point:
                if snuke_bool and point in queue_from_s:
                    snuke_bool = False
                    visited_f[point] = True

                if visited_f[point]:
                    continue
                else:
                    f_next_queue.add(point)
                    visited_f[point] = True

        n_node_f += len(f_next_queue)
        queue_from_f = f_next_queue

        if snuke_bool:
            s_next_queue = set()
            for i in queue_from_s:
                next_point = edges[i]
                for point in next_point:
                    if point in queue_from_f:
                        visited_f[i] = True
                        snuke_bool = False
                        break

                    if visited_s[point]:
                        continue
                    else:
                        s_next_queue.add(point)
                        visited_s[point] = True

            queue_from_s = s_next_queue

    if n_node_f > N // 2:
        ans = "Fennec"
    else:
        ans = "Snuke"


    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

def find_path(now, par):
    if now == n - 1:
        path.append(n - 1)
        return True
    for to in g[now]:
        if to == par: continue
        if find_path(to, now):
            path.append(now)
            return True
    return False

def dfs(now, par, color):
    color[now] = 'b'
    for to in g[now]:
        if to == par: continue
        if color[to] == "w": continue
        dfs(to, now, color)

n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b = map(int, raw_input().split())
    a -= 1; b -=1
    g[a].append(b)
    g[b].append(a)
path = []
find_path(0, -1)
path.reverse()
color = ["bl"] * n
color[0] = "b"
color[n - 1] = "w"
j = 1
k = len(path) - 2
for i in xrange(1, len(path) - 1):
    if i % 2 == 1:
        v = path[j]
        color[v] = "b"
        j += 1
    else:
        v = path[k]
        color[v] = "w"
        k -= 1
dfs(0, -1, color)
cnt = 0
for i in xrange(n):
    if color[i] == "b":
        cnt += 1
if cnt > n - cnt:
    print "Fennec"
else:
    print "Snuke"

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

def find_path(now, par):
    if now == n - 1:
        path.append(n - 1)
        return True
    for to in g[now]:
        if to == par: continue
        if find_path(to, now):
            path.append(now)
            return True
    return False

def dfs1(now, par, color):
    color[now] = "b"
    for to in g[now]:
        if to == par: continue
        if color[to] == "w": continue
        dfs1(to, now, color)

def dfs2(now, par, color):
    color[now] = "w"
    for to in g[now]:
        if to == par: continue
        if color[to] == "b": continue
        dfs2(to, now, color)

n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b = map(int, raw_input().split())
    a -= 1; b -=1
    g[a].append(b)
    g[b].append(a)
path = []
find_path(0, -1)
path.reverse()
color = ["bl"] * n
color[0] = "b"
color[n - 1] = "w"
j = 1
k = len(path) - 2
for i in xrange(1, len(path) - 1):
    if i % 2 == 1:
        v = path[j]
        color[v] = "b"
        j += 1
    else:
        v = path[k]
        color[v] = "w"
        k -= 1
dfs1(0, -1, color)
dfs2(n - 1, -1, color)
cntf = 0
cnts = 0
for i in xrange(n):
    if color[i] == "b":
        cntf += 1
    else:
        cnts += 1
if cntf > cnts:
    print "Fennec"
else:
    print "Snuke"

Solution (Python):
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 = [-1] * (n+1)
visited[1] = 0
visited[n] = 1


q = [(1,1), (n,n)]



count = [1,1]

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

  for v in d[cur]:
    if v == prev: continue
    if visited[v] != -1: continue

    chara = visited[prev]
    visited[v] = chara
    count[chara] += 1

    q.append([v, cur])


if count[0] > count[1]:
  print 'Fennec'
else:
  print 'Snuke'

Solution (Python):



import sys
sys.setrecursionlimit(int(1e6))


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.paths = [None] * (N + 1)
        for i in range(1, N + 1):
            self.paths[i] = set()

    def path(self, n1, n2):
        self.paths[n1].add(n2)
        self.paths[n2].add(n1)

    def dfs(self, n, f):
        
        if n == self.N:
            return [n]
        for nn in self.paths[n]:
            if nn != f:
                path = self.dfs(nn, n)
                if path is not None:
                    path.append(n)
                    return path
        return None

    def region(self, start, block, f):
        
        s = 1
        for nn in self.paths[start]:
            if nn != f and nn != block:
                s += self.region(nn, block, start)
        return s


def main():
    N = int(input())
    graph = Graph(N)
    for i in range(N-1):
        n1, n2 = map(int, input().split())
        graph.path(n1, n2)
    path = graph.dfs(1, None)
    l = len(path)
    fb = path[l // 2]
    sb = path[l // 2 - 1]
    fr = graph.region(1, sb, None)
    sr = graph.region(N, fb, None)
    
    
    if fr > sr:
        print("Fennec")
    else:
        print("Snuke")


main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 100)




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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


adj = []
p = []
state = []


def dfs(root, parent):
    state[root] = 1
    p[root] = parent
    for i in adj[root]:
        if i != parent:
            dfs(i, root)
    state[root] = 2


def get_size(root):
    res = 1
    for i in adj[root]:
        if i != p[root]:
            res += get_size(i)
    return res


def solve():
    global adj
    global p
    global state
    n = read_int()
    pairs = [read_int_list() for i in range(n - 1)]
    adj = [[] for i in range(n)]
    for x, y in pairs:
        x -= 1
        y -= 1
        adj[x].append(y)
        adj[y].append(x)
    state = [0] * n
    p = [-1] * n
    dfs(0, -1)

    j = n - 1
    q = []
    while j != 0:
        q.append(j)
        j = p[j]
    q.append(0)

    lq = len(q)
    half = lq // 2

    s = get_size(q[half - 1])
    if n - s > s:
        return 'Fennec'
    return 'Snuke'


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(100000000)

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

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

for x, y in xys:
    neighbors[x-1].append(y-1)
    neighbors[y-1].append(x-1)

froms = [-1 for _ in range(n)]

froms[0] = -2

def f(x):
    for y in neighbors[x]:
        if froms[y]==-1 :
            froms[y] = x
            f(y)

f(0)

path = [n-1]
while path[-1]!=0:
    if froms[path[-1]]==-1:
        break
    path.append(froms[path[-1]])
path.reverse()

blacks_l = path[:(len(path)+1)//2]
blacks = set(blacks_l)
whites = set(path[(len(path)+1)//2:])

def fennec(x):
    for y in neighbors[x]:
        if not y in blacks and not y in whites:
            blacks.add(y)
            fennec(y)

for b in blacks_l:
    fennec(b)

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

Solution (Python):


from collections import deque

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

dist_1 = [N]*(N+1)
dist_1[1] = 0


que = deque([1])
while len(que) > 0:
    a = que.popleft()
    for b in G[a]:
        if dist_1[b] > dist_1[a] + 1:
            dist_1[b] = dist_1[a] + 1
            que.append(b)
            

dist_N = [N]*(N+1)
dist_N[N] = 0


que = deque([N])
while len(que) > 0:
    a = que.popleft()
    for b in G[a]:
        if dist_N[b] > dist_N[a] + 1:
            dist_N[b] = dist_N[a] + 1
            que.append(b)
            


count_Fennec = 0
for i in range(N):
    if dist_1[i+1] <= dist_N[i+1]:
        count_Fennec += 1

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

Solution (Python):
import sys
from collections import deque

cin = sys.stdin


def line2N():
    return map(int, cin.readline().split())


N, = line2N()
adj = [[] for i in range(N+1)]
for i in range(N-1):
    u, v = line2N()
    adj[u].append(v)
    adj[v].append(u)

color = [0]*(N+1)
h_cnt = 1
t_cnt = 1
dq_head = deque([1])
color[1] = 1
dq_tail = deque([N])
color[N] = 1
for step in range(N):
    if step % 2==0:
        if not dq_head:
            t_cnt = N - h_cnt
            break
        dq_head_n = deque()
        for u in dq_head:
            for v in adj[u]:
                if color[v]==0:
                    color[v] = 1
                    dq_head_n.append(v)
                    h_cnt += 1
        dq_head = dq_head_n

    else:
        if not dq_tail:
            h_cnt = N - t_cnt
            break
        dq_tail_n = deque()
        for u in dq_tail:
            for v in adj[u]:
                if color[v]==0:
                    color[v] = 2
                    dq_tail_n.append(v)
                    t_cnt += 1
        dq_tail = dq_tail_n


if h_cnt > t_cnt:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def search(prev, start, stop):
    global nodes, edges
    for neigh in nodes[start]:
        if neigh==prev:
            continue
        if neigh==stop:
            return [stop,start]
        res=search(start,neigh,stop)
        if res!=False:
            res.append(start)
            return res
    return False

def size(prev, curr):
    su=1
    global nodes, edges
    for neigh in nodes[curr]:
        if neigh==prev:
            continue
        su+=size(curr,neigh)
    return su

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

res=search(-1,n-1,0)

fennec=(len(res)-1)//2
snuke=fennec+1
snuke=res[snuke]
fennec=res[fennec]
fennecsize=size(snuke,fennec)
snukesize=size(fennec,snuke)

if fennecsize>snukesize:
    print ("Fennec")
else:
    print("Snuke")

Solution (Python):
n = input()
G = [[] for i in xrange(n)]
for i in xrange(n-1):
    a, b = map(int, raw_input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

from collections import deque
deq = deque()
deq.append((0, 0))
deq.append((n-1, 1))
C = [None]*n
C[0] = 0; C[n-1] = 1
while deq:
    v, col = deq.popleft()
    for t in G[v]:
        if C[t] is None:
            C[t] = col
            deq.append((t, col))
B = C.count(0)
W = C.count(1)
if B == W:
    print "Snuke"
elif B < W:
    print "Snuke"
elif B > W:
    print "Fennec"