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: Runtime Error

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

import numpy as np

n = raw_input()
n = int(n)

black_tree = np.zeros([n,n],dtype = np.uint8)

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

black = np.tile([n],n)
white = np.tile([n],n)

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

black_before_list = []
white_before_list = []

#black_tree = np.array(tree,dtype=np.uint8)
#white_tree = np.array(tree,dtype=np.uint8)

white_tree = np.array(black_tree,dtype=np.uint8)

i = 0
while np.amax(black) >= n or np.amax(white) >= n:
    #print i
    if i >= 1:
        black_before_list = np.where(black == i-1)
        white_before_list = np.where(white == i-1)
        black_before_list = black_before_list[0]
        white_before_list = white_before_list[0]
    black_i_list = np.where(black == i)
    white_i_list = np.where(white == i)
    black_i_list = black_i_list[0]
    white_i_list = white_i_list[0]
    black_tree[:,black_before_list] = 0
    white_tree[:,white_before_list] = 0
    black_next_list = np.where(black_tree[black_i_list] == 1)
    white_next_list = np.where(white_tree[white_i_list] == 1)
    black_next_list = black_next_list[1]
    white_next_list = white_next_list[1]
    black[black_next_list] = i + 1
    white[white_next_list] = i + 1

#    print "black\t", black
#    print "white\t", white

    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: Runtime Error

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

import numpy as np

n = raw_input()
n = int(n)

black_tree = np.zeros([n,n],dtype = np.uint8)

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

black = np.tile([n],n)
white = np.tile([n],n)

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

black_before_list = []
white_before_list = []

#black_tree = np.array(tree,dtype=np.uint8)
#white_tree = np.array(tree,dtype=np.uint8)

white_tree = np.array(black_tree,dtype=np.uint8)

i = 0
while np.amax(black) >= n or np.amax(white) >= n:
    print i
    if i >= 1:
        black_before_list = np.where(black == i-1)
        white_before_list = np.where(white == i-1)
        black_before_list = black_before_list[0]
        white_before_list = white_before_list[0]
    black_i_list = np.where(black == i)
    white_i_list = np.where(white == i)
    black_i_list = black_i_list[0]
    white_i_list = white_i_list[0]
    black_tree[:,black_before_list] = 0
    white_tree[:,white_before_list] = 0
    black_next_list = np.where(black_tree[black_i_list] == 1)
    white_next_list = np.where(white_tree[white_i_list] == 1)
    black_next_list = black_next_list[1]
    white_next_list = white_next_list[1]
    black[black_next_list] = i + 1
    white[white_next_list] = i + 1

#    print "black\t", black
#    print "white\t", white

    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: Runtime Error

Solution code:
n = input()
edge = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, raw_input().split())
    a -= 1
    b -= 1
    edge[a] += [b]
    edge[b] += [a]

path = []
color = [0] * n
def dfs(x, y, last = -1):
    global path
    path += [x]
    if x == y:
        return True
    for to in edge[x]:
        if to == last:continue
        if dfs(to, y, x):return
    path = path[:-1]

dfs(0, n-1)
l = 0
r = len(path) - 1
turn = 0
while l < r:
    if turn == 0:
        color[l] = 1
        l += 1
    else:
        color[r] = -1
        r -= 1
    turn ^= 1


def dfs2(x, last = -1):
    global color
    if color[x] == 0:return
    for to in edge[x]:
        if to == last:continue
        color[to] = color[x]
        dfs2(to, x)
    
    
for i in range(n):
    dfs2(i)

if sum(color) >= 0:
    print "Fennec"
else:
    print "Snuke"

Submission status: Runtime Error

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]
        if m_node == N:
            break;
        is_already_pass[m_node - 1] = True
        is_leaf_node = True
        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: Runtime Error

Solution code:
import sys


def _rec(pos, n, edges, path, visited):
    if pos in visited:
        return None
    visited.add(pos)
    if pos == n:
        return path
    for to_node in edges[pos]:
        if to_node in visited:
            continue
        path.append(to_node)
        ret = _rec(to_node, n, edges, path, visited)
        if ret is not None:
            return ret
        path.pop()
    return None


def _count(pos, invalid, edges, visited):
    if pos in visited:
        return 0
    visited.add(pos)
    all = 0
    for edge in edges[pos]:
        if edge != invalid:
            all += _count(edge, pos, edges, visited) + 1
    return all


def _main(n, edges):
    visited = set()
    path = _rec(1, n, edges, [1], visited)
    if len(path) % 2 == 0:
        fennec_pos = path[len(path) / 2 - 1]
        sunuke_pos = path[len(path) / 2]
    else:
        fennec_pos = path[len(path) / 2]
        sunuke_pos = path[len(path) / 2 + 1]
    visited = set()
    fennec_count = _count(fennec_pos, sunuke_pos, edges, visited)
    visited = set()
    sunuke_count = _count(sunuke_pos, fennec_pos, edges, visited)
    #print fennec_count, sunuke_count
    if fennec_count >= sunuke_count:
        return "Fennec"
    else:
        return "Snuke"


def main():
    global nodes
    n = int(sys.stdin.readline())
    edges = {}
    for i in xrange(n - 1):
        (node_a, node_b) = sys.stdin.readline().rstrip().split()
        node_a = int(node_a)
        node_b = int(node_b)
        edges.setdefault(node_a, []).append(node_b)
        edges.setdefault(node_b, []).append(node_a)
    print _main(n, edges)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


def _rec(pos, n, edges, path, visited):
    if pos in visited:
        return None
    visited.add(pos)
    if pos == n:
        return path
    for to_node in edges[pos]:
        if to_node in visited:
            continue
        path.append(to_node)
        ret = _rec(to_node, n, edges, path, visited)
        if ret is not None:
            return ret
        path.pop()
    return None


def _count(pos, invalid, edges, visited):
    if pos in visited:
        return 0
    visited.add(pos)
    all = 0
    for edge in edges[pos]:
        if edge != invalid:
            all += _count(edge, pos, edges, visited) + 1
    return all


def _main(n, edges):
    visited = set()
    path = _rec(1, n, edges, [1], visited)
    if len(path) % 2 == 0:
        fennec_pos = path[len(path) / 2 - 1]
        sunuke_pos = path[len(path) / 2]
    else:
        fennec_pos = path[len(path) / 2]
        sunuke_pos = path[len(path) / 2 + 1]
    visited = set()
    fennec_count = _count(fennec_pos, sunuke_pos, edges, visited)
    visited = set()
    sunuke_count = _count(sunuke_pos, fennec_pos, edges, visited)
    #print fennec_count, sunuke_count
    if fennec_count >= sunuke_count:
        return "Fennc"
    else:
        return "Sunuke"


def main():
    global nodes
    n = int(sys.stdin.readline())
    edges = {}
    for i in xrange(n - 1):
        (node_a, node_b) = sys.stdin.readline().rstrip().split()
        node_a = int(node_a)
        node_b = int(node_b)
        edges.setdefault(node_a, []).append(node_b)
        edges.setdefault(node_b, []).append(node_a)
    print _main(n, edges)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


def _rec(pos, n, edges, path, visited):
    if pos in visited:
        return None
    visited.add(pos)
    if pos == n:
        return path
    for to_node in edges[pos]:
        if to_node in visited:
            continue
        path.append(to_node)
        ret = _rec(to_node, n, edges, path, visited)
        if ret is not None:
            return ret
        path.pop()
    return None


def _count(pos, invalid, edges, visited):
    if pos in visited:
        return 0
    visited.add(pos)
    all = 0
    for edge in edges[pos]:
        if edge != invalid:
            all += _count(edge, pos, edges, visited) + 1
    return all


def _main(n, edges):
    visited = set()
    path = _rec(1, n, edges, [1], visited)
    if len(path) % 2 == 0:
        fennec_pos = path[len(path) / 2]
        sunuke_pos = path[len(path) / 2 + 1]
    else:
        fennec_pos = path[len(path) / 2]
        sunuke_pos = path[len(path) / 2 + 1]
    visited = set()
    fennec_count = _count(fennec_pos, sunuke_pos, edges, visited)
    visited = set()
    sunuke_count = _count(sunuke_pos, fennec_pos, edges, visited)
    #print fennec_count, sunuke_count
    if fennec_count >= sunuke_count:
        return "Fennc"
    else:
        return "Sunuke"


def main():
    global nodes
    n = int(sys.stdin.readline())
    edges = {}
    for i in xrange(n - 1):
        (node_a, node_b) = sys.stdin.readline().rstrip().split()
        node_a = int(node_a)
        node_b = int(node_b)
        edges.setdefault(node_a, []).append(node_b)
        edges.setdefault(node_b, []).append(node_a)
    print _main(n, edges)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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:
        for m_node in node_list:
            new_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.popleft()
        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:
        for b_mas in black_mas_node:
            new_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)

        for w_mas in white_mas_node:
            new_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: Runtime Error

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());d=lambda s:csgraph.dijkstra(csr_matrix(([1]*n,(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: Runtime Error

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());d=lambda s:csgraph.dijkstra(csr_matrix(([1]*n,(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: Runtime Error

Solution code:

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:
                    #print("updated")
                    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 search(self):
        global N
        a=1
        b=N-1
        visit=[0]*(N+1)

        Qa=[a]
        Qb=[b]
        visit[a]=visit[b]=1

        while True:
            

            try:
                a=Qa.pop()
            except:
                res="Snuke"
                break


            sss=list(self.adj[a])
            if len(sss)==0:
                res="Snuke"
                break

            #print(sss)
            for sa in sss:
                if not visit[sa]:
                    Qa.append(sa)
                    visit[sa]=1

            try:
                b=Qb.pop()
            except:
                res="Fennec"
                break

            sss=list(self.adj[b])
            if len(sss)==0:
                res="Fennec"
                break

            for sb in sss:
                if not visit[sb]:
                    Qb.append(sb)
                    visit[sb]=1



            if sum(visit)==N-1:
                break


        print(res)



N=int(input())

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


g.search()

Submission status: Runtime Error

Solution code:
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:
                    #print("updated")
                    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 search(self):
        global N
        a=1
        b=N-1
        visit=[0]*(N+1)

        Qa=[a]
        Qb=[b]
        visit[a]=visit[b]=1

        while True:
            

            try:
                a=Qa.pop()
            except:
                res="Snuke"
                break


            sss=list(self.adj[a])
            if len(sss)==0:
                res="Snuke"
                break

            #print(sss)
            for sa in sss:
                if not visit[sa]:
                    Qa.append(sa)
                    visit[sa]=1

            try:
                b=Qb.pop()
            except:
                res="Fennec"
                break

            sss=list(self.adj[b])
            if len(sss)==0:
                res="Fennec"
                break

            for sb in sss:
                if not visit[sb]:
                    Qb.append(sb)
                    visit[sb]=1



            if sum(visit)==N-1:
                break


        print(res)



N=int(input())

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


g.search()

Submission status: Runtime Error

Solution code:
import numpy as np
import math

N=int(input())
nei_lst=[[] for _ in range(N+1)]

for i in range(N-1):
    n, m=[int(_) for _ in input().split()]
    nei_lst[n].append(m)
    nei_lst[m].append(n)
    
visited_lst=[False for _ in range(N+1)]
visited_lst[1]=True


via_lst=[]#経由地記憶
stack=[1]#行ける場所
while True:
    n=stack[-1]
    visited_lst[n]=True
    via_lst.append(n)
    stack.pop()
    
    if n==N:
        break
    
    isTip=True
    for m in nei_lst[n]:
        if not(visited_lst[m]):
            stack.append(m)
            isTip=False
    if isTip:
        via_lst.pop()
        

idx=math.floor((len(via_lst)-1)/2)
nei_lst[via_lst[idx]].remove(via_lst[idx+1])


visited_lst=[False for _ in range(N+1)]
visited_lst[1]=True

count=0
stack=[1]

while len(stack)>0:
    n=stack[-1]
    visited_lst[n]=True
    stack.pop()
    count+=1
    
    for m in nei_lst[n]:
        if not(visited_lst[m]):
            stack.append(m)
            
if count>N-count:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:

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:
                    #print("updated")
                    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



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.bermn_ford(1)
b2=g.bermn_ford(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: Runtime Error

Solution code:
# coding: utf-8

import collections


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.paths = collections.defaultdict(set)

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

    def dfs(self, n, f):
        # fからNへの最短経路を探す
        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):
        # startからblockを経由せず行ける範囲のnode数
        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)
    # print(fr)
    # print(sr)
    if fr > sr:
        print("Fennec")
    else:
        print("Snuke")


main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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