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: Wrong Answer

Solution code:
#!/usr/bin/python

import sys

def main(argv):
    N = int(sys.stdin.readline())
    while N:
        tree = [[] for i in xrange(0, N)]
        for i in xrange(0, N - 1):
            a, b = map(lambda x: int(x) - 1, raw_input().split(" ", 2))
            tree[a].append(b)
            tree[b].append(a)

        fennec = set([0])
        snuke = set([N - 1])
        intersection = fennec.intersection(snuke)
        while len(intersection) == 0:
            for f in fennec:
               fennec = fennec.union(set(tree[f]))
            fennec -= snuke
            for s in snuke:
               snuke = snuke.union(set(tree[s]))

            intersection = fennec.intersection(snuke)
        snuke -= intersection

        if len(fennec) > len(snuke):
            print("Fennec")
        else:
            print("Snuke")


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

if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
import collections

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

dq = collections.deque()
dq.append((0, 0, [])) 
dist = [-1 for i in range(n)]
found = False

while dq and not found:
    node, d, path = dq.popleft()
    dist[node] = d
    path.append(node)
    for nn in graph[node]:
        if nn == n-1:
            path.append(nn)
            if len(path) == 2:
                print('Snuke')
                exit()
            cen = path[(len(path)//2)]
            nex = path[(len(path)//2)+1]
            found = True
        if dist[nn] > -1:
            continue
        dq.append((nn, d+1, path[:]))

cnt = 0
dq = collections.deque()
dq.append((cen, 0))
dist = [-1 for i in range(n)]
while dq:
    node, d= dq.popleft()
    if node == nex:
        continue
    cnt += 1
    dist[node] = d
    for nn in graph[node]:
        if dist[nn] > -1:
            continue
        dq.append((nn, d+1))
if n//2 < cnt:
    print('Fennec')
else:
    print('Snuke ')

Submission status: Wrong Answer

Solution code:
e = []
N = map(int, raw_input())
for i in range(N[0]-1):
    ai,bi= map(int, raw_input().split())
    if ai > bi:
        tmp = ai
        ai = bi
        bi = tmp
    e.append((ai,bi))
e2 = e[:]
shortest = []
v = []
v.append((1,1))
for i,j in v:
    for s,t in e:
        if s==j :
            v.append((s,t))
            #shortest,append((s,t))
            e.remove((s,t))
            
        # if t == j:
        #     v.append((t,s))
        #     #shortest,append((s,t))
        #     e.remove((s,t))
    if j == N[0]-1:
        break
del v[0]
s = []
num = 0
# i,j = v[-1]
# del v[-1]
k = N[0]
# print(v)
# print(e2)
for i,j in (v[::-1]):
    if j == k:
        num += 1
        k = i

        e2.remove((i,j))

# print(e2)
# print(num)
kuro = []
kuro.append((1,1))
for i,j in kuro:
    for s,t in e2:
        if s==j :
            kuro.append((s,t))
            e2.remove((s,t))
lenkuro = len(kuro)
if (num-1) % 2 == 1:
    lenkuro += 1
lenshiro = len(e2)
if lenshiro > lenkuro:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys

def main(argv):
    N = int(sys.stdin.readline())
    while N:
        fennec = [[] for i in xrange(0, N)]
        snuke = [[] for i in xrange(0, N)]
        for i in xrange(0, N - 1):
            a, b = map(lambda x: int(x) - 1, raw_input().split(" ", 2))
            if a <= b:
                fennec[a].append(b)
                snuke[b].append(a)
            else:
                fennec[b].append(a)
                snuke[a].append(b)

        f_set = set([0])
        s_set = set([N - 1])
        intersection = f_set.intersection(s_set)
        while len(intersection) == 0:
            for f in f_set:
               f_set = f_set.union(set(fennec[f]))
            for s in s_set:
               s_set = s_set.union(set(snuke[s]))

            intersection = f_set.intersection(s_set)

        f_set = f_set - set([N - 1])
        if len(f_set) > (len(s_set) - len(intersection)):
            print("Fennec")
        else:
            print("Snuke")


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

if __name__ == "__main__":
    main(sys.argv)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N - 1))

    b = 1
    w = 1
    for i in A:
        j = sorted(i)
        if j[0] == 1:
            b += 1
            num = j[1]
        elif j[1] == N:
            w += 1

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

main()

Submission status: Wrong Answer

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

import numpy as np
        
# class Tree(object):
#     """docstring for Tree"""
#     def __init__(self, arg):
#         self.arg = arg
        
#     self.parent = hoge
#     self.child = []



N = input()

MAX_SIZE = N
MAX_VALUE = 0x10000000
# グローバル変数
visited = [False] * MAX_SIZE
cost = [MAX_VALUE] * MAX_SIZE
prev = [None] * MAX_SIZE
edges = [[0 for k in range(0, N)] for k in range(0, N)]

# f = [1]
# s = [N]

for i in range(0, N - 1):
    edge = list(map(int, raw_input().split()))
    edges[edge[0] - 1][edge[1] - 1] = 1
    edges[edge[1] - 1][edge[0] - 1] = 1

# np.sort(np.array(edges), axis=1)


def search(start):
    cost[start] = 0
    prev[start] = start
    while True:
        min = MAX_VALUE
        next = -1
        visited[start] = True
        for i in xrange(MAX_SIZE):
            if visited[i]: continue
            if edges[start][i]:
                d = cost[start] + edges[start][i]
                if d < cost[i]:
                    cost[i] = d
                    prev[i] = start
            if min > cost[i]:
                min = cost[i]
                next = i
        start = next
        if next == -1: break
    # 経路の表示
    # for i in xrange(MAX_SIZE):
    #     print "%d, prev = %d, cost = %d" %  (i, prev[i], cost[i])

    ways = np.array([cost[i] - cost[MAX_SIZE - 1] for i in range(0, MAX_SIZE)])
    if abs(sum(ways[ways < 0])) > abs(sum(ways[ways > 0])):
        print 'Fennec'
    else:
        print 'Snuke'
    # if 

    # minimum_way = [MAX_SIZE - 1]
    # i = MAX_SIZE    
    # while i != 0:
    #     minimum_way.append(prev[i - 1])
    #     i = prev[i - 1]
    # minimum_way.reverse()
    # print minimum_way

search(0)
# search(MAX_SIZE - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
Roads = []
for i in range(N-1):
    Roads.append(input().split())
black = 0
black_list = []
white = 0
white_list = []

for i in Roads:
    if 1 in i and N not in i:
        black += 1
    if N in i and 1 not in i:
        white += 1


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

Submission status: Wrong Answer

Solution code:
N = int(input())
tr = [[] for i in range(N)]

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

def canGoCnt(start, oppo):
    stack = [start]
    visited = [0 for i in range(N)]
    count = 0
    while stack:
        a = stack.pop()
        visited[a] = 1
        count += 1
        for b in tr[a]:
            if visited[b] == 0 and b != oppo:
                stack.append(b)
    return count-1

f = canGoCnt(0,N-1)
s = canGoCnt(N-1,0)
print ('Fennec' if f > s else 'Snuke')

Submission status: Wrong Answer

Solution code:
N = int(input())
tr = [[] for i in range(N)]

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

def canGoCnt(start, oppo):
    stack = [start]
    visited = [0 for i in range(N)]
    count = 0
    while stack:
        a = stack.pop()
        visited[a] = 1
        count += 1
        for b in tr[a]:
            if visited[b] == 0 and b != oppo:
                stack.append(b)
    return count-1

f = canGoCnt(0,N-1)
s = canGoCnt(N-1,0)
print ('Fennec' if f >= s else 'Snuke')

Submission status: Wrong Answer

Solution code:
N = int(input())
Roads = []
for i in range(N-1):
    Roads.append(input().split())
black = 0
black_list = []
white = 0
white_list = []

for i in Roads:
    if 1 in i:
        black += 1
    if N in i:
        white += 1


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

Submission status: Wrong Answer

Solution code:
x = int(input())

if x % 2 ==0:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

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

distance_ = a[N-1]

def get_close(a,i):
    l = list(sorted([(a[x],x) for x in d[i]]))
    return l[0][1]

tmp = N-1
for i in range(distance_ //2-1):
   tmp = get_close(a,tmp)

middle_a = get_close(a,tmp)
middle_b = tmp



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))
"""
print(a)
print(b)
print(middle_a)
print(middle_b)
print(a_new,b_new)
"""
if sum( q<99999999999999999 for q in a_new ) >sum( q<99999999999999999 for q in b_new ):
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

distance_ = a[N-1]

def get_close(a,i):
    l = list(sorted([(a[x],x) for x in d[i]]))
    return l[0][1]

tmp = N-1
for i in range(distance_ //2):
   tmp = get_close(a,tmp)

middle_a = get_close(a,tmp)
middle_b = tmp

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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def main():
  N = int(input())
  G = dict()
  for i in range(1,N+1):
    G[i] = []
  for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
  F = set()
  Q = [1]
  while Q:
    a = Q.pop(0)
    for b in G[a]:
      if b != N and b not in F:
        Q.append(b)
    F.add(a)
  S = set()
  Q = [N]
  while Q:
    a = Q.pop(0)
    for b in G[a]:
      if b != 1 and b not in S:
        Q.append(b)
    S.add(a)
  if len(F) > len(S):
    print('Fennec')
  else:
    print('Snuke')

main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def main():
  N = int(input())
  G = dict()
  for i in range(1,N+1):
    G[i] = []
  for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
  F = set()
  Q = [1]
  while Q:
    a = Q.pop(0)
    for b in G[a]:
      if b != N and b not in F:
        Q.append(b)
    F.add(a)
  S = set()
  Q = [N]
  while Q:
    a = Q.pop(0)
    for b in G[a]:
      if b != 1 and b not in S:
        Q.append(b)
    S.add(a)
  if len(F) >= len(S):
    print('Fennec')
  else:
    print('Snuke')

main()

Submission status: Wrong Answer

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 = [0 for _ in range(N)]
    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

#print(get_distance(0))
#print(get_distance(N-1))

x = get_distance(0)
max_ = math.ceil(x[N-1]/2)

val = (sum(a<= max_   for a in  x ))

if val > N//2:
    print("Fennec")
else:
    print("Snuke")
#route to -1
#0
#N-1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
g = [set() for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].add(b-1)
    g[b-1].add(a-1)


def dfs(s, e, flag):
    visited = [-1]*n
    visited[0] = 0
    cnt = 1
    if flag: temp = [[s, [[0]]]]
    else: temp = [[s]]
    lst = []
    while temp:
        p = temp.pop()
        for a in g[p[0]]:
            if flag: q = p[1][:]
            if visited[a] != -1:continue
            visited[a] = visited[p[0]] + 1
            if flag: q.append([a])
            if a == e:
                lst = q[:]
                return lst
            if flag: temp.append([a, q])
            else: temp.append([a])
            cnt += 1
    return cnt

lst = dfs(0, n-1, True)

m = (len(lst) - 1) // 2
g[lst[m][0]].discard(lst[m+1][0])
g[lst[m+1][0]].discard(lst[m][0])

c0 = dfs(0, n-1, False)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
M = N - 1
graph = [[] for _ in range(N + 1)]
dis_f = []
dis_s = []
#フェネックの距離
for i in range(M):
    a,b = map(int,input().rstrip().split(" "))
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (N + 1)
dist[0] = 0
dist[1] = 0
d = deque()
d.append(1)
while(d):
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)
    ans_f = dist[1:]
    
#すぬけくんの距離

dist = [-1] * (N + 1)
dist[0] = 0
dist[N] = 0
d = deque()
d.append(N)
while(d):
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)
    ans_s = dist[1:]

count_f = 0
count_s = 0
for i in range(N):
    if(ans_f[i] <= ans_s[i]):
        count_f += 1
    else:
        count_s += 1
if(count_f > count_s):
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

L=[[] for i in range(n+1)]

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

fe=[0 for i in range(n+1)]
que=[(1,0)]
visited=[0 for i in range(n+1)]
visited[1]=1
head=0

while len(que)>head:
    now=que[head]
    head+=1
    fe[now[0]]=now[1]
    for nex in L[now[0]]:
        if visited[nex]==0:
            visited[nex]=1
            que.append((nex,now[1]+1))
            
sn=[0 for i in range(n+1)]
que=[(n,0)]
visited=[0 for i in range(n+1)]
visited[-1]=1
head=0

while len(que)>head:
    now=que[head]
    head+=1
    sn[now[0]]=now[1]
    for nex in L[now[0]]:
        if visited[nex]==0:
            visited[nex]=1
            que.append((nex,now[1]+1))

kaname=[]
for i in range(1,n+1):
    ck=fe[i]-sn[i]
    if ck==1 or ck==2:
        kaname.append(i)

cnt=0
que=[(1,0)]
visited=[0 for i in range(n+1)]
visited[1]=1
head=0

while len(que)>head:
    now=que[head]
    head+=1
    cnt+=1
    for nex in L[now[0]]:
        if visited[nex]==0 and not nex in kaname:
            visited[nex]=1
            que.append((nex,now[1]+1))

if cnt*2>n:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

ignore = [0] * N
route = []

# nowからNまでのルート
def bfs(now, goal, array):
    pos = deque([[now, array]])

    while pos[0][0] != goal:
        u, arr = pos.popleft()
        ignore[u] = 1

        for i in dist[u]:
            if ignore[i] != 1:
                newarray = copy.deepcopy(arr)
                newarray.append(i)
                pos.append([i, newarray])

    return pos[0][1]

# NG以外のところで辿れるところの数
def dfs_ter(sta, ng):
    pos = deque([sta])

    ignore = [0] * N
    for i in ng:
        ignore[i] = 1

    cnt = 0
    while len(pos) > 0:
        u = pos.popleft()
        ignore[u] = 1
        cnt += 1
        for i in dist[u]:
            if ignore[i] != 1:
                pos.append(i)

    return cnt

# ルート探索
route = bfs(0, N - 1, [0])

L = len(route)
fen_ter = route[:(L + 2 - 1) // 2]
snu_ter = route[(L + 2 - 1) // 2:]

fen_ans = dfs_ter(0, snu_ter)

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

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

ignore = [0] * N
route = []

# nowからNまでのルート
def dfs(now, goal, array):
    pos = deque([[now, array]])

    while pos[0][0] != goal:
        u, arr = pos.popleft()
        ignore[u] = 1

        for i in dist[u]:
            if ignore[i] != 1:
                newarray = copy.deepcopy(arr)
                newarray.append(i)
                pos.append([i, newarray])

    return pos[0][1]

# NG以外のところで辿れるところの数
def dfs_ter(sta, ng):
    pos = deque([sta])

    ignore = [0] * N
    for i in ng:
        ignore[i] = 1

    cnt = 0
    while len(pos) > 0:
        u = pos.popleft()
        ignore[u] = 1
        cnt += 1
        for i in dist[u]:
            if ignore[i] != 1:
                pos.append(i)

    return cnt

# ルート探索
route = dfs(0, N - 1, [0])

L = len(route)
fen_ter = route[:(L + 2 - 1) // 2]
snu_ter = route[(L + 2 - 1) // 2:]

fen_ans = dfs_ter(0, snu_ter)
snu_ans = dfs_ter(N - 1, fen_ter)

if snu_ans >= fen_ans:
    print('Snuke')
else:
    print('Fennec')

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

ignore = [0] * N
route = []

# nowからNまでのルート
def dfs(now, goal, array):
    global route
    if now == goal:
        route = array
        return

    ignore[now] = 1

    for i in dist[now]:
        if ignore[i] != 1:
            newarray = copy.deepcopy(array)
            newarray.append(i)
            dfs(i, goal, newarray)

    ignore[now] = 0

# ルート探索
dfs(0, N - 1, [0])

# NG以外のところで辿れるところの数
def dfs_ter(sta, ng):
    pos = deque([sta])

    ignore = [0] * N
    for i in ng:
        ignore[i] = 1

    cnt = 0
    while len(pos) > 0:
        u = pos.popleft()
        ignore[u] = 1
        cnt += 1
        for i in dist[u]:
            if ignore[i] != 1:
                pos.append(i)

    return cnt

L = len(route)
fen_ter = route[:(L + 2 - 1) // 2]
snu_ter = route[(L + 2 - 1) // 2:]

fen_ans = dfs_ter(0, snu_ter)
snu_ans = dfs_ter(N - 1, fen_ter)

if snu_ans >= fen_ans:
    print('Snuke')
else:
    print('Fennec')

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]
    adjlist = {}
    for a, b in AB:
        adjlist.setdefault(a-1, [])
        adjlist.setdefault(b-1, [])
        adjlist[a-1].append(b-1)
        adjlist[b-1].append(a-1)
    import collections
    q = collections.deque([[0, []]])
    shortest = None
    while q:
        v, path = q.popleft()
        path = path+[v]
        if v == N-1:
            shortest = collections.deque(path[1:-1])
            break
        for nxt in adjlist[v]:
            q.append([nxt, path])
    assert shortest is not None, "bfs error"
    
    # print(adjlist)
    # print(shortest)
    b_nexts = set(adjlist[0])
    b_nexts.discard(N-1)
    w_nexts = set(adjlist[N-1])
    w_nexts.discard(0)

    colored = [False for _ in range(N)]
    colored[0] = True
    colored[N-1] = True
    b_turn = True
    while True:
        # print(colored)
        # print(b_nexts)
        # print(w_nexts)
        # print(shortest)
        if b_turn:
            if len(b_nexts) == 0:
                print("Snuke")
                return
            if len(shortest) > 0:
                nxt = shortest.popleft()
                b_nexts.remove(nxt)
            else:
                nxt = b_nexts.pop()
            if nxt in w_nexts:
                w_nexts.remove(nxt)
        else:
            if len(w_nexts) == 0:
                print("Fennec")
                return
            if len(shortest) > 0:
                nxt = shortest.pop()
                w_nexts.remove(nxt)
            else:
                nxt = w_nexts.pop()
            if nxt in b_nexts:
                b_nexts.remove(nxt)
        # print(nxt)
        colored[nxt] = True
        for v in adjlist[nxt]:
            if colored[v] is False:
                if b_turn:
                    b_nexts.add(v)
                else:
                    w_nexts.add(v)
        
        b_turn = not b_turn
    #print("Snuke" if b_turn else "Fennec")


if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]
    adjlist = {}
    for a, b in AB:
        adjlist.setdefault(a-1, [])
        adjlist.setdefault(b-1, [])
        adjlist[a-1].append(b-1)
        adjlist[b-1].append(a-1)
    import collections
    q = collections.deque([[0, []]])
    shortest = None
    while q:
        v, path = q.popleft()
        path = path+[v]
        if v == N-1:
            shortest = collections.deque(path[1:-1])
            break
        for nxt in adjlist[v]:
            q.append([nxt, path])
    assert shortest is not None, "bfs error"
    
    # print(adjlist)
    # print(shortest)
    b_nexts = set(adjlist[0])
    b_nexts.discard(N-1)
    w_nexts = set(adjlist[N-1])
    w_nexts.discard(0)

    colored = [False for _ in range(N)]
    colored[0] = True
    colored[N-1] = True
    b_turn = True
    while all(colored) is False:
        # print(colored)
        # print(b_nexts)
        # print(w_nexts)
        # print(shortest)
        if b_turn:
            if len(b_nexts) == 0:
                print("Snuke")
                return
            if len(shortest) > 0:
                nxt = shortest.popleft()
                b_nexts.remove(nxt)
            else:
                nxt = b_nexts.pop()
            if nxt in w_nexts:
                w_nexts.remove(nxt)
        else:
            if len(w_nexts) == 0:
                print("Fennec")
                return
            if len(shortest) > 0:
                nxt = shortest.pop()
                w_nexts.remove(nxt)
            else:
                nxt = w_nexts.pop()
            if nxt in b_nexts:
                b_nexts.remove(nxt)
        #print(nxt)
        colored[nxt] = True
        for v in adjlist[nxt]:
            if colored[v] is False:
                if b_turn:
                    b_nexts.add(v)
                else:
                    w_nexts.add(v)
        
        b_turn = not b_turn
    print("Snuke" if b_turn else "Fennec")


if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]
    adjlist = {}
    for a, b in AB:
        adjlist.setdefault(a-1, [])
        adjlist.setdefault(b-1, [])
        adjlist[a-1].append(b-1)
        adjlist[b-1].append(a-1)
    import collections
    q = collections.deque([[0, []]])
    shortest = None
    while q:
        v, path = q.popleft()
        path = path+[v]
        if v == N-1:
            shortest = set(path[1:-1])
            break
        for nxt in adjlist[v]:
            q.append([nxt, path])
    assert shortest is not None, "bfs error"
    
    # print(adjlist)
    # print(shortest)
    b_nexts = set(adjlist[0])
    b_nexts.discard(N-1)
    w_nexts = set(adjlist[N-1])
    w_nexts.discard(0)
    colored = [False for _ in range(N)]
    colored[0] = True
    colored[N-1] = True
    b_turn = True
    while all(colored) is False:
        # print(colored)
        # print(b_nexts)
        # print(w_nexts)
        # print(shortest)
        if b_turn:
            if len(b_nexts) == 0:
                print("Snuke")
                return
            intsecs = b_nexts & shortest
            if len(intsecs) > 0:
                nxt = intsecs.pop()
                b_nexts.remove(nxt)
                shortest.remove(nxt)
            else:
                nxt = b_nexts.pop()
            if nxt in w_nexts:
                w_nexts.remove(nxt)
        else:
            if len(w_nexts) == 0:
                print("Fennec")
                return
            intsecs = w_nexts & shortest
            if len(intsecs) > 0:
                nxt = intsecs.pop()
                w_nexts.remove(nxt)
                shortest.remove(nxt)
            else:
                nxt = w_nexts.pop()
            if nxt in b_nexts:
                b_nexts.remove(nxt)
        #print(nxt)
        colored[nxt] = True
        for v in adjlist[nxt]:
            if colored[v] is False:
                if b_turn:
                    b_nexts.add(v)
                else:
                    w_nexts.add(v)
        
        b_turn = not b_turn
    print("Snuke" if b_turn else "Fennec")


if '__main__' == __name__:
    resolve()