Problem:


Score : 400 points

Problem Statement

Fennec and Snuke are playing a board game.

On the board, there are N cells numbered 1 through N, and N-1 roads, each connecting two cells. Cell a_i is adjacent to Cell b_i through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.

Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored.
Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell.
More specifically, each player performs the following action in her/his turn:

Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.

Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.

A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.

Constraints

2 \leq N \leq 10^5

1 \leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

If Fennec wins, print Fennec; if Snuke wins, print Snuke.

Sample Input 1

7
3 6
1 2
3 1
7 4
5 7
1 4

Sample Output 1

Fennec

For example, if Fennec first paints Cell 2 black, she will win regardless of Snuke's moves.

Sample Input 2

4
1 4
4 2
2 3

Sample Output 2

Snuke



Sample input:
7
3 6
1 2
3 1
7 4
5 7
1 4


Sample output:
Fennec

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
# coding: utf-8
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]

# -1: not yet, 0: fennec, 1: sunuke
visited = [-1] * (n+1)
visited[1] = 0
visited[n] = 1

# 0 == fennec, 1 == sunuke
q = [(1,1), (n,n)]

# 0: fennec
# 1: sunuke
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'

# TLE
# while len(q) > 0:
#   cur, prev, sunuke = q.pop(0)
#   # print cur,prev,sunuke

#   if visited[cur]:
#     continue

#   visited[cur] = True
#   if sunuke:
#     count_s += 1
#   else:
#     count_f += 1

#   for v in d[cur]:
#     q.append([v, cur, sunuke])

# if count_f > count_s:
#   print 'Fennec'
# else:
#   print 'Snuke'

Submission status: Accepted

Solution code:
# coding: utf-8


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

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 100)

# sys.stdin = open('d1.in')


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# D

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 form 1
dist_1 = [N]*(N+1)
dist_1[1] = 0

# BFS
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 form N
dist_N = [N]*(N+1)
dist_N[N] = 0

# BFS
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
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')

Submission status: Accepted

Solution code:
import sys
from collections import deque

cin = sys.stdin
# cin = open("in.txt", "r")

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:
from networkx import*
N,*t=map(str.split,open(0))
s=shortest_path_length
x=s(G:=Graph(t),'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(*N)::2])

Submission status: Runtime Error

Solution code:
#!python3

class Node:

    def __init__(self, num):
        self.num = num
        self.v = 1
        self.parent = 0
        self.deep = None


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

# input
N = int(input())
AB = [LI() for _ in range(N - 1)]

# link
link = [[] for _ in range(N + 1)]
for a, b in AB:
    link[a].append(b)
    link[b].append(a)

# nodes
nodes = [Node(i) for i in range(N + 1)]


def create_tree(parent):
    for child in link[parent.num]:
        if child == parent.parent:
            continue
        node = nodes[child]
        node.parent = parent.num
        node.deep = parent.deep + 1
        create_tree(node)
        parent.v += node.v


def main():
    nodes[1].deep = 1
    create_tree(nodes[1])

    x = (nodes[N].deep - nodes[1].deep - 1) // 2
    v = nodes[N]
    for _ in range(x):
        v = nodes[v.parent]
    
    snuke = v.v
    fennec = N - snuke
    ans = "Fennec" if fennec > snuke else "Snuke"
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!python3

class Node:

    def __init__(self, num):
        self.num = num
        self.v = 1
        self.parent = None
        self.deep = None


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

# input
N = int(input())
AB = [LI() for _ in range(N - 1)]

# link
link = [[] for _ in range(N + 1)]
for a, b in AB:
    link[a].append(b)
    link[b].append(a)

# nodes
nodes = [Node(i) for i in range(N + 1)]


def create_tree(parent):
    for child in link[parent.num]:
        if child == parent.parent:
            continue
        node = nodes[child]
        node.parent = parent.num
        node.deep = parent.deep + 1
        create_tree(node)
        parent.v += nodes[child].v


def main():
    nodes[1].deep = 1
    create_tree(nodes[1])

    x = (nodes[N].deep - nodes[1].deep - 1) // 2
    v = nodes[N]
    for _ in range(x):
        v = nodes[v.parent]
    
    snuke = v.v
    fennec = N - snuke
    ans = "Fennec" if fennec > snuke else "Snuke"
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

from collections import deque


def submit():
    n = int(input())
    edge = {i: [] for i in range(1, n + 1)}
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge[a].append(b)
        edge[b].append(a)

    # 1とNの最短路を求める
    def dfs(q, path, hist):
        p = q.pop()
        if p == n:
            return path

        for e in edge[p]:
            if not hist[e]:
                q.append(e)
                path.append(e)
                hist[e] = True
                ret = dfs(q, path, hist)
                if ret:
                    return ret
                path.pop(-1)
        return None


    q = deque()
    q.append(1)
    hist = {i: False for i in range(n + 1)}
    hist[1] = True
    direct_path = dfs(q, [1], hist)
    d = len(direct_path) 
    if d % 2:
        fennec = direct_path[:d // 2 + 1]
        snuke = direct_path[d // 2 + 1:]
    else:
        fennec = direct_path[:d // 2]
        snuke = direct_path[d // 2:]

    edge[fennec[-1]].remove(snuke[0])
    
    # fennecが取れる数を数える
    color = 0
    picked = [False for _ in range(n)]
    q = deque()
    q.append(1)
    picked[0] = True
    while len(q):
        p = q.pop()
        color += 1
        for e in edge[p]:
            if not picked[e - 1]:
                q.append(e)
                picked[e - 1] = True
    
    if color > n - color:
        print("Fennec")
    else:
        print("Snuke")


submit()

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(N)]
F=[0 for i in range(N)]
A=[]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
  A.append([a,b])
  
def dfs(s,R):
  F[s]=1
  
  if s==N-1:
    return [s]
  else:
    for n in G[s]:
      if F[n]==0:
        k=dfs(n,R)
        if len(k)!=0:
          k.append(s)
          return k
     
  return []
  
root=dfs(0,[])
#print(root[::-1])
p=root[::-1][len(root)//2+len(root)%2-1]
q=root[::-1][len(root)//2+len(root)%2]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N) 
for i in range(N-1):
  a,b=map(int,A[i])
  if a==p and b==q:
    continue
  if a==q and b==p:
    continue
  uf.union(a, b)

scoreA=uf.size(0)
scoreB=N-scoreA
#print(scoreA,scoreB)

if scoreA>scoreB:
  print("Fennec")
else:
  print("Snuke")

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(N)]
F=[0 for i in range(N)]
A=[]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
  A.append([a,b])
  
root=[]
def dfs(s):
  flag=0
  F[s]=1
  if s!=N-1:
    for n in G[s]:
      if F[n]==0:
        j=dfs(n)
        if j==1:
          flag=1
  else:
    flag=1
  if flag==1:
    root.append(s)
  return flag
  
dfs(0)
#print(root[::-1])
p=root[::-1][len(root)//2+len(root)%2-1]
q=root[::-1][len(root)//2+len(root)%2]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N) 
for i in range(N-1):
  a,b=map(int,A[i])
  if a==p and b==q:
    continue
  if a==q and b==p:
    continue
  uf.union(a, b)

scoreA=uf.size(0)
scoreB=N-scoreA
#print(scoreA,scoreB)

if scoreA>scoreB:
  print("Fennec")
else:
  print("Snuke")

Submission status: Runtime Error

Solution code:
N=int(input())
A=[0 for _ in range(N)]
G=[[] for i in range(N)]
F=[0 for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
  
root=[]
def dp(s):
  flag=0
  F[s]=1
  l=1
  for n in G[s]:
    if F[n]==0:
      i,j=dp(n)
      l+=i
      if j==1:
        flag=1
      
  A[s]=l
  if s==N-1:
    flag=1
  if flag==1:
    root.append(s)
  return l,flag
  
dp(0)
#print(A,root)

m=root[::-1][len(root)//2+len(root)%2-1]
scoreA=A[0]-A[m]+1
scoreB=N-scoreA
#print(scoreA,scoreB,m)

if scoreA>scoreB:
  print("Fennec")
else:
  print("Snuke")

Submission status: Runtime Error

Solution code:
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=[[0,[0]]]
v=[0]*n
v[0]=1
f=0
while True:
    p=q.pop(0)
    #if p[1][-1]==n-1:
        #break
    v[p[0]]=1
    for i in g[p[0]]:
        if v[i]==0:
            v[i]=1
            if i==n-1:
                r=p[1]+[i]
                f=1
                break
                q.append([i,p[1]+[i]])
    if f==1:
        break
fe=r[:(-(-len(r)//2))]
v=[0]*n
v[(-(-len(r)//2))]=1
v[0]=1
while fe:
    s=fe.pop(0)
    for i in g[s]:
        if v[i]==0:
            fe.append(i)
            v[i]=1
x=sum(v)-1
y=n-x
if x>y:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
tree = [[] for i in range(N+1)]

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

dist_fennec = [100001] * (N+1)
dist_snuke = [100001] * (N+1)
q = [1]
dist[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist_fennec[next] == 100001:
            dist_fennec[next] = dist_fennec[now] + 1
            q.append(next)

q = [N]
dist[N] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist_snuke[next] == 100001:
            dist_snuke[next] = dist_snuke[now] + 1
            q.append(next)

fennec, snuke = 0, 0
for i in range(1, N+1):
    if dist_snuke[i] <= dist_fennec[i]:
        fennec += 1
    else:
        snuke += 1

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

Submission status: Runtime Error

Solution code:

import math
N = int(input())
graph = {}
SCORE = 0
def dfs(visted,v,depth):
    visted[v] = depth
    for next_v in graph[v]:
        if  visted[next_v]  == -1 :
            dfs(visted,next_v,depth + 1)




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

    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)

vF = [-1] * (N + 1)
vF[1] = 0
dfs(vF,1,0)
# print(vF)

vS = [-1] * (N + 1)
vS[N] = 0

dfs(vS,N,0)
# print(vS)

fc = 0
sc = 0

for f,s in zip(vF[1:N + 1],vS[1:N + 1]):
    if f <= s:
        fc += 1
    else:
        sc += 1

# print(fc,sc)
if fc > sc:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not x==y: # 根が同じでない場合のみ併合する
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] # 要素数を併合
                self.par[x] = y # 根を付け替えている
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
        
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y) 

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    from collections import defaultdict
    G = defaultdict(list)
    D = []
    for i in range(N-1):
        a, b = map(int,input().split())
        D.append([a,b])
        G[a].append(b)
        G[b].append(a)
    que = [[1,[1]]]
    visited = {}
    
    while que != []:
        v = que.pop()
        visited[v[0]] = 1
        if v[0] == N:
            path = v[1]
            break
        else:
            for i in G[v[0]]:
                if not i in visited:
                    que.append([i,v[1]+[i]])
    L = len(path)
    d1,d2 = path[L//2],path[L//2+1]
    G2 = UnionFind(N)
    
    for i in D:
        a,b = i
        if not ((a==d1 and b==d2) or (a==d2 and b==d1)):
            G2.union(a,b)
    one = -G2.par[G2.find(1)]
    enu = -G2.par[G2.find(N)]
    
    if one>enu:
        print("Fennec")
    else:
        print("Snuke")
    

main()

Submission status: Runtime Error

Solution code:
N = int(input())

ab = [[] for _ in range(N)]

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

dF = [0] * N
dS = [0] * N
def dfs(now, d, dlist, visited):
    
    if visited[now] == False:
        dlist[now] = d
        visited[now] = True

        for next in ab[now]:
            dfs(next, d+1, dlist, visited)


vF = [False] * N
dfs(0,0,dF, vF)
vS = [False] * N
dfs(N-1, 0, dS, vS)

cnt_F = 0
cnt_S = 0
for i in range(N):
    if dF[i] <= dS[i]:
        cnt_F += 1
    else:
        cnt_S += 1

#print(dF, dS)
if cnt_F > cnt_S:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
N = int(input())

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

col = [ -1 for i in range(N)]

col[0] = 0

p = []
def dfs(n,c,path):
    global p
    path = path + [n]
    if n == N - 1:
        p = path
    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            dfs(v,c+1,path)
dfs(0,0,[])

if len(p) % 2 ==0:
    fn = p[len(p)//2-1]
    sn = p[len(p)//2]
else:
    fn = p[len(p)//2]
    sn = p[len(p)//2+1]


colfn = [ -1 for i in range(N)]
colfn[0] = 0
def dfs2(n,c):

    for v in e[n]:
        if v == sn:
            continue
        elif colfn[v] == -1:
            colfn[v] = c + 1
            dfs2(v,c+1)

dfs2(0,0)

colsn = [ -1 for i in range(N)]
colsn[N-1] = 0
def dfs3(n,c):

    for v in e[n]:
        if v == fn:
            continue
        elif colsn[v] == -1:
            colsn[v] = c + 1
            dfs3(v,c+1)

dfs3(N-1,0)
fennec = -1
snuke = -1
for i in range(N):
    if colsn[i] != -1:
        snuke += 1
    if colfn[i] != -1:
        fennec += 1

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

Submission status: Runtime Error

Solution code:
N = int(input())

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

col = [ -1 for i in range(N)]
col[0] = 0
def dfs(n,c):
    if not e[n]:
        return

    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            dfs(v,c+1)

dfs(0,0)

colf = [ -1 for i in range(N)]
colf[0] = 0
def dfsf(n,c):

    if not e[n]:
        return
    for v in e[n]:
        if v == N - 1:
            #colf[v] = c + 1
            continue
        elif colf[v] == -1:
            colf[v] = c + 1
            dfsf(v,c+1)
dfsf(0,0)

cols = [ -1 for i in range(N)]
cols[N-1] = 0
def dfss(n,c):
    
    if not e[n]:
        return

    for v in e[n]:
        if v == 0:
            #cols[v] = c + 1
            continue
        elif cols[v] == -1:
            cols[v] = c + 1
            dfss(v,c+1)
dfss(N-1,0)



fennec,snuke = 0,0

for i in range(N):
    if colf[i] != -1:
        fennec += 1
    if cols[i] != -1:
        snuke += 1

t = col[N-1] - 1
if t % 2 == 0:
    fennec += (t//2)
    snuke += (t//2)
else:
    fennec += (t//2) + 1
    snuke += (t//2)
    
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")