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: Time Limit Exceeded

Solution code:
N = int(input())

inf = float('inf')

import heapq
def dijkstra(adj, n, st=1):
    dj = [inf] * (n + 1)
    paths = dict((x, [x]) for x in range(n + 1))
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                paths[tn] = paths[fn] + [tn]
                heapq.heappush(q, (dj[tn], tn))
    return dj, paths

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

costs, paths = dijkstra(adj, N, 1)
main_street = paths[N]
import math
mid = math.ceil(len(main_street) / 2) - 1
mid_v0 = main_street[mid]
mid_v1 = main_street[mid + 1]
adj[mid_v0] = filter(lambda x: x[0] != mid_v1, adj[mid_v0])
adj[mid_v1] = filter(lambda x: x[0] != mid_v0, adj[mid_v1])

snuke = dijkstra(adj, N, 1)[0].count(inf)
fennec = dijkstra(adj, N, N)[0].count(inf)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
  a, b = map(int, input().split())
  T[a - 1].append(b - 1)
  T[b - 1].append(a - 1)
def dijkstra(N, s0):
  D = [N] * N
  Q = [s0]
  D[s0] = 0
  while Q:
    s = Q[0]
    Q = Q[1:]
    for adj in T[s]:
      if D[s] + 1 < D[adj]:
        D[adj] = D[s] + 1
        Q.append(adj)
  return D
D1 = dijkstra(N, 0)
D2 = dijkstra(N, N - 1)
score = 0
for i in range(N):
  score += 1 if D1[i] <= D2[i] else -1
print('Fennec' if score > 0 else 'Snuke')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

f = [[0], []]
d = 1

f[1] = f[1] + p[0]

while 1:
    if n - 1 in f[d]:
        break
    temp = []
    for i in f[d]:
        temp = [] + p[i]
    temp = list(set(temp))
    f.append([])
    d += 1
    f[d] = [] + temp

route = [n - 1]
t = n - 1
for i in range(d, 0, -1):
    for j in f[i - 1]:
        if t in p[j]:
            t = j
            route.append(t)

#print(f)
#print(route)

mid = route[ len(route) // 2 - 1 ]

#print(mid)

f = [[0], []]
d = 1

f[1] = f[1] + p[0]

check = 1
if mid in f[1]:
    f[1].remove(mid)
    if len(f[1]) == 0:
        check = 0

while check:
    temp = []
    for i in f[d]:
        temp = [] + p[i]
    temp = list(set(temp))
    if mid in temp:
        temp.remove(mid)
    for i in f[d - 1]:
        if i in temp:
            temp.remove(i)
    if len(temp) == 0:
        break
    f.append([])
    d += 1
    f[d] = [] + temp

fe = sum(len(v) for v in f)

mid = route[ len(route) // 2 ]

f = [[n - 1], []]
d = 1

f[1] = f[1] + p[n - 1]

check = 1
if mid in f[1]:
    f[1].remove(mid)
    if len(f[1]) == 0:
        check = 0

while check:
    temp = []
    for i in f[d]:
        temp = [] + p[i]
    temp = list(set(temp))
    if mid in temp:
        temp.remove(mid)
    for i in f[d - 1]:
        if i in temp:
            temp.remove(i)
    if len(temp) == 0:
        break
    f.append([])
    d += 1
    f[d] = [] + temp

sn = sum(len(v) for v in f)

if fe > sn:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

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

def BFS(i):
  dist=[0]*N
  d=[-1]*N
  d[i]=0#未訪問ならd=-1,訪問済みならiからの距離
  que=[i]
  dist=1
  while que:
    for j in range(len(que)):
      label=que.pop(0)+1
      for i in range(N-1):
        if ab[i][0]==label and d[ab[i][1]-1]==-1:
          d[ab[i][1]-1]=dist
          que+=[ab[i][1]-1]
        if ab[i][1]==label and d[ab[i][0]-1]==-1:
          d[ab[i][0]-1]=dist
          que+=[ab[i][0]-1]
    dist+=1
  return(d)

dist1=BFS(0)
dist2=BFS(N-1)
Fe=0
Su=0
for i in range(N):
  if dist1[i]<=dist2[i]:
    Fe+=1
  else:
    Su+=1
if Fe>Su:
  print("Fennec")
else:
  print("Snuke")

Submission status: Time Limit Exceeded

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

n = raw_input()
n = int(n)

tree = []

i = 0
while i < n:
    tree.append([])
    i += 1

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

black = [n]*n
white = [n]*n

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

i = 0
while max(black) >= n and max(white) >= n:
    black_next_list = []
    black_i_list = []
    while i in black:
        black_i = black.index(i)
        black_next_list.extend(tree[black_i])
        black[black_i] = n
        black_i_list.append(black_i)

    for black_i in black_i_list:
        black[black_i] = i

    for black_next in black_next_list:
        if black[black_next - 1] < i:
            pass
        else:
            black[black_next - 1] = i + 1

    white_next_list = []
    white_i_list = []
    while i in white:
        white_i = white.index(i)
        white_next_list.extend(tree[white_i])
        white[white_i] = n
        white_i_list.append(white_i)

    for white_i in white_i_list:
        white[white_i] = i

    for white_next in white_next_list:
        if white[white_next - 1] < i:
            pass
        else:
            white[white_next - 1] = i + 1

    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: Time Limit Exceeded

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

n = raw_input()
n = int(n)

tree = []

i = 0
while i < n:
    tree.append([])
    i += 1

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

#print tree

black = [n]*n
white = [n]*n

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

#print black
#print white

i = 0
while i < n:
    #print i
    black_next_list = []
    black_i_list = []
    while i in black:
        black_i = black.index(i)
        #print tree[black_i]
        black_next_list.extend(tree[black_i])
        black[black_i] = n
        black_i_list.append(black_i)

    for black_i in black_i_list:
        black[black_i] = i

    for black_next in black_next_list:
        if black[black_next - 1] < i:
            pass
        else:
            black[black_next - 1] = i + 1

    #print "black", black

    white_next_list = []
    white_i_list = []
    while i in white:
        white_i = white.index(i)
        #print tree[white_i]
        white_next_list.extend(tree[white_i])
        white[white_i] = n
        white_i_list.append(white_i)

    for white_i in white_i_list:
        white[white_i] = i

    for white_next in white_next_list:
        if white[white_next - 1] < i:
            pass
        else:
            white[white_next - 1] = i + 1

    #print "white", white
    i += 1

#print black
#print white

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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict 
 
N = int(input())
 
g = defaultdict(list)
for i in range(N-1):
    a, b = input().split()
    g[a].append(b)
    g[b].append(a)
 
score = { "f" : 1, "s" : 1 }
front = { "f": ["1"], "s":[str(N)] }
prev  = { "f": [], "s":[] }
opp = { "f" : "s", "s" : "f" }

for i in range(N):
    if i % 2 == 0:
        t = "f"
    else:
        t = "s"

    node = front[t]
    nn = []
    for n in node:
        for x in g[n]:
            if x not in front["s"] and x not in front["f"] and x not in prev["s"] and x not in prev["f"]:
                nn.append(x)
                score[t] += 1
    if nn:
        prev[t] = front[t]
        front[t] = nn
    else:
        score[opp[t]] = N - score[t]
        break
 
if score["f"] > score["s"]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict 
 
N = int(input())
 
g = defaultdict(list)
for i in range(N-1):
    a, b = input().split()
    g[a].append(b)
    g[b].append(a)
 
q = [("f", ["1"]), ("s", [str(N)])]
score = { "f" : 0, "s" : 0 }
front = { "f": ["1"], "s":[str(N)] }
opp = { "f" : "s", "s" : "f" }

while q:
    t, node = q.pop(0)
    nn = []
    for n in node:
        for x in g[n]:
            if x not in node and x not in front[opp[t]]:
                nn.append(x)
                score[t] += 1

    if nn:
        front[t] = nn
        q.append( (t, nn) )
 
if score["f"] > score["s"]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict 

N = int(input())

g = defaultdict(list)
for i in range(N-1):
    a, b = input().split()
    g[a].append(b)
    g[b].append(a)

q = [("f", ["1"]), ("s", [str(N)])]
score = { "f" : 0, "s" : 0 }
f = ["1", str(N)]
while q:
    t, node = q.pop(0)
    nn = []
    for n in node:
        for x in g[n]:
            if x not in f:
                nn.append(x)
                f.append(x)
                score[t] += 1
    if nn:
        q.append( (t, nn) )

if score["f"] > score["s"]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

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

import re

n = int(raw_input())

m = [[] for i in range(n)]
b_list = [0]
w_list = [n-1]
ans = [0]*n
ans[0] = 1
ans[n-1] = -1

for i in range(n-1):
        tmp = map(int, re.split('\s', raw_input()))
        m[tmp[0]-1].append(tmp[1]-1)
        m[tmp[1]-1].append(tmp[0]-1)


def solve(x):
        global b_list, w_list
        tmp = 0
        for i in range(n):
                if (ans[i] == 0):
                        tmp += 1
        if (tmp == 0):
                return 0
        n_list = []

        li = b_list
        if (x == -1):
                li = w_list
        for i in li:
                for j in m[i]:
                        if (ans[j] == 0):
                                n_list.append(j)
        for i in list(set(n_list)):
                ans[i] = x
        if (x == 1):
                b_list = n_list
        else:
                w_list = n_list
        solve(x * (-1))

solve(1)

b = 0
w = 0

for i in range(n):
        if (ans[i] == 1):
                b += 1
        else:
                w += 1

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#Python
import sys

N=input()
a=[[] for i in range(N+1)]

for i in range(N-1):
    u,v=list(map(int,raw_input().split()))
    a[u].append(v)
    a[v].append(u)

#print a

#初期化
kyori=(N+1)*[0]

sys.setrecursionlimit(1000000)
#深さ優先探索
def dfs(Graph, Start, Visited=None):
	if (Visited==None):  Visited = [] #開始点のときに探索済みリストをつくる
	Visited.append(Start)  #現在の頂点を探索済みリストに加える
	#print(Start, "\n", Visited)  #現在の頂点と探索済みリストを表示
	for Next in Graph[Start]:  #次に探索する頂点の候補
		#print "Next::"+str(Next)
		if ( Next in Visited ):  continue  #訪問済みリストにある頂点は飛ばす
		kyori[Next]=kyori[Start]+1
		dfs(Graph, Next, Visited)  #再帰
	return kyori


kyori_from_start=dfs(a,1)


kyori=(N+1)*[0]
dfs(a,N)




f_p=0
s_p=0
for k in range(1,N+1):
	if kyori_from_start[k]<=kyori[k]:
		f_p+=1
	else:
		s_p+=1

#print f_p
#print s_p

if f_p>s_p:
	print 'Fennec'
else:
	print 'Snuke'

Submission status: Time Limit Exceeded

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

import re

n = int(raw_input())

m = [[] for i in range(n)]
ans = [0]*n
ans[0] = 1
ans[n-1] = -1

for i in range(n-1):
        tmp = map(int, re.split('\s', raw_input()))
        m[tmp[0]-1].append(tmp[1]-1)
        m[tmp[1]-1].append(tmp[0]-1)

def solve(x):
        tmp = 0
        for i in range(n):
                if (ans[i] == 0):
                        tmp += 1
        if (tmp == 0):
                return 0
        li = []
        for i in range(n):
                if (ans[i] == x):
                        for j in m[i]:
                                if (ans[j] == 0):
                                        li.append(j)
        for i in list(set(li)):
                ans[i] = x
        solve(x * (-1))

solve(1)
b = 0
w = 0

for i in range(n):
        if (ans[i] == 1):
                b += 1
        else:
                w += 1

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

Submission status: Time Limit Exceeded

Solution code:
#Python

N = input()
#print N

a = [[0 for j in range(N+1)] for i in range(N+1)]

for i in range(N-1):
	l=map(int, raw_input().split())
	#print l[0]
	#print l[1]
	a[l[0]][l[1]]=1
	a[l[1]][l[0]]=1
#print a


v=(N+1)*[0]
kyori=(N+1)*[0]


def visit(i):
	v[i]=1
	#print v

	for j in range(1,N+1):

		#print "*i::"+str(i)+" "+"j::"+str(j)
		if a[i][j] == 1 and v[j] == 0:
			#print str(i)+"==>"+str(j)

			kyori[j]=kyori[i]+1

			#print "dist::"+str(dist)
			visit(j)


visit(1)
kyori_from_start=kyori
#print kyori_from_start


#Initialize
v=(N+1)*[0]
kyori=(N+1)*[0]


visit(N)
#print kyori

f_p=0
s_p=0
for k in range(1,N+1):
	if kyori_from_start[k]<=kyori[k]:
		f_p+=1
	else:
		s_p+=1

#print f_p
#print s_p

if f_p>s_p:
	print 'Fennec'
else:
	print 'Snuke'

Submission status: Time Limit Exceeded

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

import copy

def now_land(land, op):
    tmp = []
    for i in range(len(land)):
        if land[i] == op:
            tmp.append(i)
    return tmp

def nxt_land(route, now):
    tmp = []
    for i in range(len(route)):
        for j in range(len(now)):
            if route[i][0] == now[j] + 1:
                tmp.append(route[i][1])
            if route[i][1] == now[j] + 1:
                tmp.append(route[i][0])
    return tmp

def chg(land, nxt, op):
    if land[nxt - 1] == -1:
        land[nxt - 1] = op
        return 1, land
    else:
        return 0, land
    

def wide_search(q, route, op):
    tmp = []
    ct = 0
    while len(q) != 0:
        land = q.pop(0)
        now = now_land(land, op)
        nxt = nxt_land(route, now)
        for i in nxt:
            t_land = copy.deepcopy(land)
            rt, t_land = chg(t_land, i, op)
            if rt == 1:
                tmp.append(t_land)
    return len(tmp), tmp

def MAIN(land, route):
    q = [copy.deepcopy(land)]
    while True:
        rt, q = wide_search(q, route, 0)
        if rt == 0:
            print "Snuke"
            break
        rt, q = wide_search(q, route, 1)
        if rt == 0:
            print "Fennec"
            break

if __name__ == '__main__':
    n = input()

    route = []
    route.sort(key = lambda x:x[0])
    land = [-1 for i in range(n)]
    land[0] = 0
    land[len(land) - 1] = 1

    for i in range(n - 1):
        route.append(map(int, raw_input().split()))
    
    MAIN(land, route)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(n):
    depth = 0
    que = deque()
    que.append([n, depth])
    dist = {}
    dist[str(n)] = 0
    while(len(que)):
        tmp_n, tmp_d = que.popleft()
        if(tmp_n in a or tmp_n in b):
            for i in range(N-1):
                if(a[i]==tmp_n):
                    if(str(b[i]) not in dist):
                        dist[str(b[i])] = tmp_d+1
                        que.append([b[i], tmp_d+1])
                elif(b[i]==tmp_n):
                    if(str(a[i]) not in dist):
                        dist[str(a[i])] = tmp_d+1
                        que.append([a[i], tmp_d+1])
    return dist

dist_1 = bfs(0)
dist_N = bfs(N-1)

res = 0
for i in range(N):
    if(dist_1[str(i)]<=dist_N[str(i)]):
        res += 1
if(res>N-res):
    print("Fennec")
else:
    print("Snuke")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(n):
    depth = 0
    que = deque()
    que.append([n, depth])
    dist = {}
    dist[str(n)] = 0
    while(len(que)):
        tmp_n, tmp_d = que.popleft()
        for i in range(N-1):
            if(a[i]==tmp_n):
                if(str(b[i]) not in dist):
                    dist[str(b[i])] = tmp_d+1
                    que.append([b[i], tmp_d+1])
            elif(b[i]==tmp_n):
                if(str(a[i]) not in dist):
                    dist[str(a[i])] = tmp_d+1
                    que.append([a[i], tmp_d+1])
    return dist

dist_1 = bfs(0)
dist_N = bfs(N-1)

res = 0
for i in range(N):
    if(dist_1[str(i)]<=dist_N[str(i)]):
        res += 1
if(res>N-res):
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7


def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        adj[a].append(b)
        adj[b].append(a)

    queue = deque([0])
    visit = [-1] * N
    visit[0] = 0

    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1

    queue = deque([N-1])
    visit2 = [-1] * N
    visit2[N-1] = 0

    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit2[u] < 0:
                queue.append(u)
                visit2[u] = visit2[now] + 1

    cnt = 0
    for i in range(N):
        if visit[i] <= visit2[i]:
            cnt += 1
    print('Fennec') if cnt > N-cnt else print('Snuke')
    # print(visit2)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}

    #頂点の追加
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0

        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    #辺の追加
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    #辺を除く
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]


    #Walkの追加
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.adjacent

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    #距離
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.adjacent}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    #ある1点からの距離
    def distance_all(self,u):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.adjacent}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        return T

    #最短路
    def shortest_path(self,u,v):
        from collections import deque
        T={v:None for v in self.vertex}

        if u==v:
            return [u]

        Q=deque([u])
        T[u]=u
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if not T[x]:
                    T[x]=w
                    Q.append(x)
                    if x==v:
                        P=[v]
                        a=v
                        while a!=u:
                            a=T[a]
                            P.append(a)
                        return P[::-1]
        return None
#================================================
from collections import deque
N=int(input())
G=Graph(range(1,N+1))

for _ in range(N-1):
    a,b=map(int,input().split())
    G.add_edge(a,b)

sp=G.shortest_path(1,N)
dist=len(sp)-1

u,v=sp[dist//2],sp[dist//2+1]
G.remove_edge(u,v)

A=len(G.connected_component(1))
B=len(G.connected_component(N))

if A>B:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
N = int(input())
graph = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]
is_visited = [False for i in range(N+1)]
q = []
heapq.heappush(q, (0, 0, 1))
t2f = {}
while q:
    c, f, t = heapq.heappop(q)
    t2f[t] = f
    if t == N:
        break
    for nt in graph[t]:
        if is_visited[nt]:
            continue
        heapq.heappush(q, (c+1, t, nt))
        is_visited[nt] = True
is_visited = [False for i in range(N+1)]
is_visited[1] = True
is_visited[N] = True
for i in range((c-1)//2):
    t = t2f[t]
    is_visited[t] = True
q = []
heapq.heappush(q, (0, 1))
ans = 0
while q:
    c, t = heapq.heappop(q)
    ans += 1
    for nt in graph[t]:
        if is_visited[nt]:
            continue
        heapq.heappush(q, (c+1, nt))
        is_visited[nt] = True
if N // 2 < ans:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs(G, root):
    n = len(G)
    Parents = [-1] * n
    Depth = [0] * n
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        for v in G[u]:
            if visited[v]:
                continue
            else:
                dq2 += [v]
                Depth[v] = Depth[u] + 1
                Parents[v] = u
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return Depth, Parents


Depth, Parents = bfs(Edge, 0)
cnt = (Depth[-1] - 1)//2
now = N-1
while cnt:
    cnt -= 1
    now = Parents[now]
Edge[Parents[now]].remove(now)

Q = deque()
Q.append(0)
Done = [0] * N
Done[0] = 1
ans = 1
while Q:
    now = Q.popleft()
    for nex in Edge[now]:
        if Done[nex]:
            continue
        else:
            Q.append(nex)
            Done[nex] = 1
            ans += 1

if ans > N // 2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

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):
    visited = [-1]*n
    visited[s] = 0
    temp = [s]
    lst = []
    while temp:
        p = temp.pop()
        for a in g[p]:
            if visited[a] != -1:continue
            visited[a] = visited[p] + 1
            temp.append(a)
    return visited

lst0 = dfs(0)
lstn = dfs(n-1)
cnt = 0
for i in range(n):
    if lst0[i] <= lstn[i]: cnt += 1

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

Submission status: Accepted

Solution code:
import typing
from typing import List, NamedTuple, Deque, Set, Counter

class node:
    def __init__(self, id: int) -> None:
        self.id: int = id
        self.parent: node = self
        self.root: node = self
        self.rank: int = 0
        self.connection: List[node] = []

    def addConnection(self, other: 'node') -> None:
        self.connection.append(other)
        other.connection.append(self)

    def delConnection(self, other: 'node') -> None:
        self.connection.remove(other)
        other.connection.remove(self)

    def setParent(self, other: 'node') -> None:
        self.parent = other
        self.rank = other.rank +1
    
    def setRoot(self, other: 'node') -> None:
        self.root = other

    def setAsRoot(self) -> None:
        self.parent = self
        self.root = self
        self.rank = 0


def makePath(root: node, target: node) -> Deque[node]:
    path: Deque[node] = Deque()
    path.append(target)
    while path[0] != root:
        path.appendleft(path[0].parent)
    return path


def bfs(root: node):
    reserved: Deque[node] = Deque([root])
    seen: Set[int] = {root.id}
    while len(reserved) > 0:
        current_node = reserved.popleft()
        for next_node in current_node.connection:
            if next_node.id in seen:
                continue
            next_node.setParent(current_node)
            next_node.setRoot(root)
            seen.add(next_node.id)
            reserved.append(next_node)


def main():
    N = int(input())
    Edge = [map(int, input().split()) for _ in range(N-1)]

    Node: List[node] = [node(i) for i in range(N)]
    for a, b in Edge:
        Node[a-1].addConnection(Node[b-1])

    #Node[0]からbfs
    bfs(Node[0])
    #between:Node[0]とNode[N-1]の間にあるノード数
    between: int = Node[N-1].rank -1
    #sep:お互い陣地を取り合った時に衝突する点までの距離fromNode[0]
    sep = (between+1)//2
    path = makePath(Node[0], Node[N-1])
    #衝突点の結合を削除, 再度bfs
    path[sep].delConnection(path[sep+1])
    path[sep+1].setAsRoot()
    bfs(path[sep+1])
    #2分した木のノード数集計
    fennec, snuke = Counter([n.root.id for n in Node]).values()
    #勝者判定
    print('Fennec' if fennec > snuke else 'Snuke')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = (int(x)-1 for x in input().split())
  graph[a].append(b)
  graph[b].append(a)

from collections import deque
def bfs(s:int)->list:
  dist = [-1]*n
  dist[s] = 0
  que = deque([s])
  while que:
    u = que.popleft()
    for v in graph[u]:
      if dist[v] != -1: continue
      dist[v] = dist[u] + 1
      que.append(v)
  return dist

dfen = bfs(0)
dsnu = bfs(n-1)
pfen = 0
psnu = 0
for i in range(n):
  if dfen[i] <= dsnu[i]: pfen += 1
  else: psnu += 1
ans = 'Fennec' if pfen > psnu else 'Snuke'
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    F = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = read_index()
        F[a].add(b)
        F[b].add(a)

    D = [0] * N
    S = deque()
    S.append((1, 0))
    S.append((-1, N - 1))
    D[0] = 1
    D[N - 1] = -1
    while S:
        c, p = S.popleft()
        for q in F[p]:
            if D[q] != 0:
                continue
            D[q] = c
            S.append((c, q))
    a = D.count(1)
    b = N - a
    print("Fennec" if a > b else "Snuke")
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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)
from collections import deque  
def dfs(k):
  visited=[-1 for i in range(N)]
  visited[k]=0
  q=deque([])
  q.append(k)
  while q:
    u=q.popleft()
    for v in graph[u]:
      if visited[v]==-1:
        visited[v]=visited[u]+1
        q.append(v)
  return visited
a=dfs(0)
b=dfs(N-1)
count=0
for i in range(N):
  if a[i]<=b[i]:
    count+=1
if count>N//2:
  print("Fennec")
else:
  print("Snuke")