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/bin/env python
# -*- coding: utf-8 -*-

import sys
import copy

def calcDist(x, i_list, j, l):
	if len(i_list) == 0:
		return N
	min = N
	for i in i_list:
		if i == j:
			return l
		i_list_c = copy.copy(chains[i])
		if x in i_list_c:
			i_list_c.remove(x)
		m = calcDist(i, i_list_c, j, l + 1)
		if min > m:
			min = m

	return min


N = int(sys.stdin.readline())

chains = {}

for i in range(0, N - 1):
	line = list(map(int, sys.stdin.readline().split(' ')))
	if not line[0] in chains:
		chains[line[0]] = []
	chains[line[0]].append(line[1])
	if not line[1] in chains:
		chains[line[1]] = []
	chains[line[1]].append(line[0])

b = 0
w = 0
for i in range(2, N):
	bd = calcDist(1, chains[1], i, 0)
	wd = calcDist(N, chains[N], i, 0)
	if bd <= wd:
		b += 1
	else:
		w += 1
	# print('bd:' + str(bd))
	# print('wd:' + str(wd))

if b > w:
	print ('Fennec')
else:
	print ('Sunuke')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import copy

def l_search(land, op):
    tmp = []

    for i in range(len(land[0]) - 1):
        print land[0][i], op
        if land[0][i] == op:
            tmp.append(i)
            print tmp
    return tmp

def nxt_l(road, land):
    tmp = []
    for i in range(len(road)):
        for j in range(len(land)):
            if road[i][0] == land[j] + 1:
                tmp.append(road[i][1])

    return tmp

def chg(land, nxt, op):
    tmp = []
    tmp = copy.deepcopy(land)
    if tmp[nxt - 1] < 0:
        tmp[nxt - 1] = op
    return 1, tmp

def black_wide_searcd(q, road):
    tmp = []
    while len(q) != 0:
        l = q.pop(0)
        #黒島を取得
        ltmp = l_search(l, 0)
        print ltmp
        nxt = nxt_l(road, ltmp)
        #次の島を黒島にする
        ct = 0
        for i in nxt:
            ct, t_land = chg(land, i, 0)
            if ct > 0:
                tmp.append(t_land)
            elif rt == 0 and i == nxt[len(nxt) - 1]:
                return "Fennic"
    return tmp, "aaa"
        
def white_wide_search(q, road):
    a = q
    tmp = []
    while len(a) != 0:
        l = a.pop(0)
        #黒島を取得
        ltmp = l_search(l, 1)
        nxt = nxt_l(road, ltmp)
        #次の島を白島にする
        rt = 0
        for i in nxt:
            ct, t_land = chg(land, i, 1) 
            rt += ct  
            if ct > 0:
                tmp.append(t_land)
            elif rt == 0 and i == nxt[len(nxt) - 1]:
                return tmp, "Sunake"
    return tmp, "aaa"
         
def battle(land, road):
    q = [[land]]
    while True:
        q , flag = black_wide_searcd(q, road)
        if flag != "aaa":
            print flag
            break
        q , flag = white_wide_search(q, road)
        if flag != "aaa":
            print flag
            break


if __name__ == '__main__':
    n = input()
    road = []
    land = [-1 for i in range(n)]
    land[0] = 0
    land[len(land) - 1] = 1

    for i in range(n - 1):
        road.append(map(int, raw_input().split()))
    
    road.sort(key = lambda x:x[0])

    battle(land, road)

Submission status: Runtime Error

Solution code:
n=input()
graph=[[] for i in range(n+1)]
for i in range(n-1):
    v,u=list(map(int,raw_input().split()))
    graph[v].append(u)
    graph[u].append(v)

dist= [-1 for i in range(n+1)]
dist[1]=0
son=[[] for i in range(n+1)]
queue=[1]
father=[0 for i in range(n+1)]
def bfs(u):
    for v in graph[u]:
        if dist[v]==-1:
            dist[v]=dist[u]+1
            son[u].append(v)
            father[v]=u
            queue.append(v)
    queue.pop(0)
    if len(queue)!=0:
        bfs(queue[0])

bfs(1)
road=[n]
tempfather=n
for i in range(dist[n]):
    road.append(father[tempfather])
    tempfather=father[tempfather]

di=len(road)
k=road[(di-2)/2]

def countson(u):
  count=0
  if len(son[u])==0:return 1
  for v in son[u]:
      count+=countson(v)
  return count+1

cs=countson(k)
cf=n-cs

if cs>=cf:print 'Snuke'
else:
    print 'Fennec'

Submission status: Runtime Error

Solution code:
# Fennec VS. Snuke
N = int(input())
p = []
for i in range(N-1):
    pi = list(map(int, input().split()))
    p.append(pi)

#隣接リスト
l = [[] for i in range(N)]
for pi in p:  #0-originedに注意
    l[pi[0]-1].append(pi[1]-1)
    l[pi[1]-1].append(pi[0]-1)

path = []

def short(N,i, p=1): #1とNの間の最短経路を探索
    path.append(i) 
    if (i == N ): # iがNに到達したらTrueを返す
        return True
    for j in l[i]: # iから到達できる候補
        if (j!=p and short(N, j, i) ):
            return True
    path.pop() #Trueを返せないのはNを含まないpathなので消す

short(N-1,1-1)

def point(i, cut, p=-1): #文節が存在するときの，i を含む木のノード数
    if (i == cut ): 
        return 1
    cnt=1
    for j in l[i]: # iから到達できる候補
        if (j!=p ): #親ノードじゃない
            cnt+=point(j, cut , i)
    return cnt

p1 = point(1-1, path[(len(path)-1)//2])
p2 = point(N-1, path[(len(path)-1)//2+1])

FP= p1
SP= max(p2, N-p1)

if ( FP>SP ):
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
# coding: utf-8
class Node:
    def __init__(self, id):
        self.id = id
        self._connection = set()
    
    def add_connection(self, node):
        self._connection.add(node)

    def get_connection(self):
        return self._connection

    def __repr__(self):
        return str(self.id)


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


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def find_path_in_tree(begin_node, target_node):
    visited_nodes = {begin_node}
    tip = begin_node

    path = [begin_node]
    level_search_cache = [tip.get_connection()]
    while True:
        search_target = level_search_cache[-1]

        if target_node in search_target:
            path.append(target_node)
            return path

        if len(search_target) == 0:
            if len(path) == 1:
                raise Exception("Target node unreacheable.")
            tip = path[-2]
            path.pop()
            level_search_cache.pop()
            continue

        next_node = search_target.pop()
        tip = next_node
        visited_nodes.add(next_node)
        path.append(tip)
        level_search_cache.append(tip.get_connection() - visited_nodes)


def populate_nodes(own_node, opponent_node):
    new_own_node = set(own_node)
    for node in own_node:
        targets = node.get_connection()
        for target in targets:
            if target in own_node or target in opponent_node:
                continue
            new_own_node.add(target)
            populate_nodes(new_own_node, opponent_node)
    return new_own_node


def main():
    N = get_ln_int_inputs()[0]
    edges = []
    for _ in range(N - 1):
        edges.append(get_ln_int_inputs())
    
    nodes = [Node(i) for i in range(N)]
    for edge in edges:
        e1, e2 = edge
        nodes[e1 - 1].add_connection(nodes[e2 - 1])
        nodes[e2 - 1].add_connection(nodes[e1 - 1])

    path_from_f_to_s = find_path_in_tree(nodes[0], nodes[-1])

    fennec_path = {nodes[0]}
    snuke_path = {nodes[N - 1]}

    for _ in range(len(path_from_f_to_s) // 2):
        snuke_path.add(path_from_f_to_s.pop())
    for node in path_from_f_to_s:
        fennec_path.add(node)

    fennec_nodes = populate_nodes(fennec_path, snuke_path)

    if len(fennec_nodes) > N - len(fennec_nodes):
        print("Fennec")
    else:
        print("Snuke")


main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
class Node:
    def __init__(self, id):
        self.id = id
        self._connection = set()
    
    def add_connection(self, node):
        self._connection.add(node)

    def get_connection(self):
        return self._connection

    def __repr__(self):
        return str(self.id)


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


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def find_path_in_tree(begin_node, target_node):
    visited_nodes = {begin_node}
    tip = begin_node

    path = [begin_node]
    level_search_cache = [tip.get_connection()]
    while True:
        search_target = level_search_cache[-1]

        if target_node in search_target:
            path.append(target_node)
            return path

        if len(search_target) == 0:
            if len(path) == 1:
                raise Exception("Target node unreacheable.")
            tip = path[-2]
            path.pop()
            level_search_cache.pop()
            continue

        next_node = search_target.pop()
        tip = next_node
        visited_nodes.add(next_node)
        path.append(tip)
        level_search_cache.append(tip.get_connection() - visited_nodes)


def populate_nodes(own_node, opponent_node):
    new_own_node = set(own_node)
    for node in own_node:
        targets = node.get_connection()
        for target in targets:
            if target in own_node or target in opponent_node:
                continue
            new_own_node.add(target)
            populate_nodes(new_own_node, opponent_node)
    return new_own_node


def main():
    N = get_ln_int_inputs()[0]
    edges = []
    for _ in range(N - 1):
        edges.append(get_ln_int_inputs())
    
    nodes = [Node(i) for i in range(N)]
    for edge in edges:
        e1, e2 = edge
        nodes[e1 - 1].add_connection(nodes[e2 - 1])
        nodes[e2 - 1].add_connection(nodes[e1 - 1])

    path_from_f_to_s = find_path_in_tree(nodes[0], nodes[-1])

    fennec_path = {nodes[0]}
    snuke_path = {nodes[N - 1]}

    for _ in range(len(path_from_f_to_s) // 2):
        snuke_path.add(path_from_f_to_s.pop())
    for node in path_from_f_to_s:
        fennec_path.add(node)

    fennec_nodes = populate_nodes(fennec_path, snuke_path)
    snuke_nodes = populate_nodes(snuke_path, fennec_path)

    if len(fennec_nodes) > len(snuke_nodes):
        print("Fennec")
    else:
        print("Snuke")


main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(sys.getrecursionlimit()*100)
n = int(input())
g = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
a = []
def f(i, p):
    a.append(i)
    if i == n:
        return True
    for j in g[i]:
        if j != p:
            if f(j, i):
                return True
    a.pop()
f(1,0)
m = (len(a)+1) // 2
def h(i, j, p):
    if i == j:
        return 1
    return 1 + sum(h(k, j, i) for k in g[i] if k != p)
if h(1, a[m], 0) > h(n, a[m-1], 0):
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
n = int(input())
g = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
a = []
def f(i, p):
    a.append(i)
    if i == n:
        return True
    for j in g[i]:
        if j != p:
            if f(j, i):
                return True
    a.pop()
f(1,0)
m = (len(a)+1) // 2
def h(i, j, p):
    if i == j:
        return 1
    return 1 + sum(h(k, j, i) for k in g[i] if k != p)
if h(1, a[m], 0) > h(n, a[m-1], 0):
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())

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

    # print(np.array(tree))

    Q = [(x, [0, x], 0) for x in tree[0]]
    reached = [1] + [0]*(N-2) + [0]
    while len(Q) > 0:
        new_pos, root, cost = Q.pop()
        reached[new_pos] = 1

        if new_pos == N-1:
            break

        #add to Q
        for p in tree[new_pos]:
            new_root = root[:]
            if reached[p] == 0:
                new_root.append(p)
                Q.append((p, new_root, cost+1))

    l = math.ceil(len(root)/2) - 1
    r = l + 1

    # print(root, l, r)
    tree[root[l]].remove(root[r])
    tree[root[r]].remove(root[l])
    # print(tree, tree)

    F = tree[0]
    S = tree[N-1]

    reached = [1] + [0]*(N-2) + [1]
    while True:
        if len(F) == 0:
            print("Snuke")
            break
        else:
            pos = F.pop()
            reached[pos] = 1
            for p in tree[pos]:
                if reached[p] == 0:
                    F.append(p)

        if len(S) == 0:
            print("Fennec")
            break
        else:
            pos = S.pop()
            reached[pos] = 1
            for p in tree[pos]:
                if reached[p] == 0:
                    S.append(p)



if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()

Submission status: Runtime Error

Solution code:
import random
def main():
      sample_list = ['Fennec','Snuke']
      random.shuffle(sample_list)
      print sample_list[1]

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [tuple(map(int,input().split())) for i in range(N-1)]

import networkx as nx
G = nx.Graph()
G.add_nodes_from(range(1,N))
G.add_edges_from(edge)
path = nx.shortest_path(G, 1, N)
pathlen = len(path)
G.remove_edges_from([(path[(pathlen)//2-1], path[(pathlen)//2])])
cut = [len(g) for g in nx.connected_components(G)]
if cut[0]-cut[1] > 0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
import random

def main():
      sample_list = ['Fennec','Snuke']
      random.shuffle(sample_list)
      print sample_list

Submission status: Runtime Error

Solution code:
import random
def a():
sample_list = ['Fennec','Snuke']
random.shuffle(sample_list)
print sample_list
return 0

Submission status: Runtime Error

Solution code:
import random
def a:
 sample_list = ['Fennec','Snuke']
 random.shuffle(sample_list)
 print sample_list

Submission status: Runtime Error

Solution code:
import random

sample_list = ['Fennec','Snuke']
random.shuffle(sample_list)
print sample_list

Submission status: Runtime Error

Solution code:
# coding: utf-8
class Node:
    def __init__(self, id):
        self.id = id
        self._connection = set()
    
    def add_connection(self, node):
        self._connection.add(node)

    def get_connection(self):
        return self._connection


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


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def find_path_in_tree(current_path_list, target_node):
    tip = current_path_list[-1]
    search_targets = tip.get_connection()

    if len(search_targets) == 0:
        return current_path_list, False

    for node in search_targets:
        if node in current_path_list:
            continue

        current_path_list.append(node)
        if node == target_node:
            return current_path_list, True

        result, is_found = find_path_in_tree(current_path_list, target_node)
        if is_found:
            return result, True
        current_path_list.pop()

    return current_path_list, False        


def populate_nodes(own_node, opponent_node):
    new_own_node = set(own_node)
    for node in own_node:
        targets = node.get_connection()
        for target in targets:
            if target in own_node or target in opponent_node:
                continue
            new_own_node.add(target)
            populate_nodes(new_own_node, opponent_node)
    return new_own_node


def main():
    N = get_ln_int_inputs()[0]
    edges = []
    for _ in range(N - 1):
        edges.append(get_ln_int_inputs())
    
    nodes = [Node(i) for i in range(N)]
    for edge in edges:
        e1, e2 = edge
        nodes[e1 - 1].add_connection(nodes[e2 - 1])
        nodes[e2 - 1].add_connection(nodes[e1 - 1])

    path_from_f_to_s, _ = find_path_in_tree([nodes[0]], nodes[N - 1])

    fennec_path = {nodes[0]}
    snuke_path = {nodes[N - 1]}

    for _ in range(len(path_from_f_to_s) // 2):
        snuke_path.add(path_from_f_to_s.pop())
    for node in path_from_f_to_s:
        fennec_path.add(node)

    fennec_nodes = populate_nodes(fennec_path, snuke_path)
    snuke_nodes = populate_nodes(snuke_path, fennec_path)

    if len(fennec_nodes) > len(snuke_nodes):
        print("Fennec")
    else:
        print("Snuke")


main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
#勝者がフェネックならば Fennec と、すぬけくんならば Snuke と出力せよ。

import sys

N = int(input())

A = {}

for i in range(N):
    B = input().split()
    A.update({int(B[0]),int(B[1])})

X = A[1]
Y = A[N-1]

if Y == X:
    print("Fennec")
    sys.exit()

for i in range(N-1):
    X = A[X]
    if X == Y:
        print("Snuke")
        sys.exit()

    Y = A[Y]
    if Y == X:
        print("Fennec")
        sys.exit()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)


N = None
G = None

BLACK = 1
WHITE = 2
GRAY  = 3

colors = None

def dfs1(v, visited):
    global N, G, colors

    if visited[v]: return

    visited[v] = True
    colors[v] = BLACK

    for dst in G[v]:
        if dst == N: continue
        dfs1(dst, visited)

def dfs2(v, visited):
    global N, G, colors

    if visited[v]: return

    visited[v] = True
    colors[v] = GRAY if colors[v] == BLACK else WHITE

    for dst in G[v]:
        if dst == 1: continue
        dfs2(dst, visited)

def main():
    global N, G, colors

    sys.setrecursionlimit(100000)

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

    for line in sys.stdin:
        a, b = map(int, line.split())
        G[a].add(b)
        G[b].add(a)

    colors = [GRAY for _ in range(N+1)]
    dfs1(1, [False for _ in range(N+1)])
    dfs2(N, [False for _ in range(N+1)])

    n_black = sum(map(lambda c: c == BLACK, colors[1:]))
    n_white = sum(map(lambda c: c == WHITE, colors[1:]))
    n_gray  = sum(map(lambda c: c == GRAY, colors[1:]))

    n1 = n_black - 1
    n2 = n_white - 1
    if n_gray % 2:
        n1 += 1

    print("Snuke" if n1 <= n2 else "Fennec")

if __name__ == "__main__": main()

Submission status: Runtime Error

Solution code:
from collections import  defaultdict
from collections import deque
import math
N = int(input())

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


d = defaultdict(list)

for a,b in AB:
    d[a-1].append(b-1)
    d[b-1].append(a-1)


def get_distance(start):
    visited = set([start,])
    distance = [999999999999999999 for _ in range(N)]
    distance[start ] =0
    to_visit = deque([ (1,a) for a in d[start]])

    while to_visit:
        dist,now = to_visit.popleft()
        visited.add(now)
        distance[now]=dist
        for a in d[now]:
            if a not in visited:
                to_visit.append((dist+1,a))

    return distance



a =(get_distance(0))
b= (get_distance(N-1))


for i in range(N):
    if a[i]==b[i] or a[i]==b[i]+1:
        middle_a = i
        #middle_b
        for j in d[i]:
            if b[j]==b[i]-1:
                middle_b = j

"""
print(a)
print(b)
print(middle_a)
print(middle_b)
"""
x = get_distance(0)
max_ = math.ceil(x[N-1]/2)





d[middle_a].remove(middle_b)
d[middle_b].remove(middle_a)

a_new = (get_distance(0))
b_new = (get_distance(N-1))
if sum( q<99999999999999999 for q in a_new ) >sum( q<99999999999999999 for q in b_new ):
    print("Fennec")
else:
    print("Snuke")
#route to -1
#0
#N-1