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

Solution (Python):

from collections import deque

N = int(input())
edge = []
for i in range(N-1):
    edge.append(list(map(int, input().split())))
    
neighbor = [[] for i in range(N)]
for node1, node2 in edge:
    neighbor[node1-1].append([node1-1, node2-1])
    neighbor[node2-1].append([node2-1, node1-1])
    
def bfs(node):
    hasVisited = [0]*N
    que = deque([])
    
    que.extend(neighbor[node])
    
    while len(que)!=0:
        prev_node, nex_node = que.popleft()
        if nex_node == node:
            pass
        elif hasVisited[nex_node]:
            pass
        elif not hasVisited[nex_node]:
            hasVisited[nex_node] = hasVisited[prev_node]+1
            que.extend(neighbor[nex_node])

    
    return hasVisited

node_B = 1
node_W = N
dist_B = bfs(node_B-1)
dist_W = bfs(node_W-1)

b_win = 0
w_win = 0
for i in range(N):
    if dist_B[i] > dist_W[i]:
        w_win += 1
    else:
        b_win += 1
        
if b_win > w_win:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import deque
n = int(input())
nodes = [list(map(int,input().split())) for _ in range(n-1)]
p = [[] for y in range(n+1)]
for node in nodes:
  p[node[0]].append(node[1])
  p[node[1]].append(node[0])

queue = deque([[1,0]])
fen = [float('inf')]*(n+1)
visited = [0]*(n+1)
visited[1] = 1
while 0 < len(queue):
  tmp = queue.popleft()
  if tmp[0] == n:
    path = tmp[1] - 1
    continue
  fen[tmp[0]] = tmp[1]
  for x in p[tmp[0]]:
    if visited[x] == 0:
      queue.append([x,tmp[1]+1])
      visited[x] = 1

queue2 = deque([[n,0]])
visited = [0]*(n+1)
visited[n] = 1
snu = [float('inf')]*(n+1)
while 0 < len(queue2):
  tmp = queue2.popleft()
  if tmp[0] == 1:
    continue
  snu[tmp[0]] = tmp[1]
  for x in p[tmp[0]]:
    if visited[x] == 0:
      queue2.append([x,tmp[1]+1])
      visited[x] = 1
countf,counts = 0,0
for i in range(1,n+1):
  if fen[i] <= snu[i]:
    countf += 1
  else:
    counts += 1
print('Fennec') if counts < countf else print('Snuke')

Solution (Python):
import sys
sys.setrecursionlimit(500000)
N = int(input())
Node = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    Node[a].append(b)
    Node[b].append(a)
Route = [1]
def dfs(n, np):
    for nc in Node[n]:
        if nc == np:
            continue
        elif nc == N:
            Route.append(N)
            return True
        else:
            Route.append(nc)
            if dfs(nc, n):
                return True
            else:
                Route.pop()
    return False

dfs(1, 0)
b = (len(Route)+1)//2
Node[Route[b-1]].remove(Route[b])
Node[Route[b]].remove(Route[b-1])

cnt = 0
def dfs2(n, np):
    global cnt
    for nc in Node[n]:
        if nc == np:
            continue
        else:
            cnt += 1
            dfs2(nc, n)

dfs2(1, 0)
cnt = -cnt
dfs2(N, 0)
if cnt >= 0:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
from collections import deque
N = int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)
adis=[0]*N
avis=[False]*N
avis[0]=True
bdis=[0]*N
bvis=[False]*N
bvis[N-1]=True
akei=deque()
akei.append(0)
bkei=deque()
bkei.append(N-1)
while akei:
    x = akei.popleft()
    for s in table[x]:
        if not avis[s]:
            adis[s]=adis[x]+1
            avis[s]=True
            akei.append(s)
while bkei:
    x = bkei.popleft()
    for s in table[x]:
        if not bvis[s]:
            bdis[s]=bdis[x]+1
            bvis[s]=True
            bkei.append(s)
white=0
brack=0
for i in range(N):
    if adis[i]<=bdis[i]:
        brack+=1
    else:
        white+=1
if white<brack:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import sys
sys.setrecursionlimit(10000000)

def m():
    def dfs(v, p, c, depth):
        depth[v] = c
        for child in graph[v]:
            if child == p:
                continue
            dfs(child, v, depth[v]+1, depth)
    n = int(input())
    graph = [[] for _ in range(n + 1)]
    depth_from1 = [0] * (n+1)
    depth_fromN = [0] * (n+1)
    depth_from1[1] = 0
    depth_fromN[n] = 0

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

    dfs(1, -1, 0, depth_from1)
    dfs(n, -1, 0, depth_fromN)
    fene = 0
    sn = 0

    for i in range(1,n+1):
        if depth_from1[i] <= depth_fromN[i]:
            fene += 1
        else:
            sn += 1
    if fene > sn:
        return "Fennec"
    else:
        return "Snuke"


print(m())

Solution (Python):
N = int(input())
g = [[] for _ in range(N+1)]

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

def BFS(v):
        d = [N]*(N+1)
        d[v] = 0
        q = [v]

        while q:
                u = q.pop()
                for i in g[u]:
                        if d[i] == N:
                                d[i] = d[u] + 1
                                q.append(i)

        return d

db = BFS(1)
dw = BFS(N)

if sum([db[i] > dw[i] for i in range(1,N+1)]) >= N/2:
        print("Snuke")
else:
        print("Fennec")

Solution (Python):
N = int(input())
g = [[] for _ in range(N+1)]

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

def BFS(v):
        d = [N]*(N+1)
        d[v] = 0
        q = [v]

        while q:
                u = q.pop()
                for i in g[u]:
                        if d[i] == N:
                                d[i] = d[u] + 1
                                q.append(i)

        return d

db = BFS(1)
dw = BFS(N)

b = 0
w = 0

for i in range(1,N+1):
        if db[i] <= dw[i]:
                b += 1
        else:
                w += 1

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

Solution (Python):
N = int(input())
G = [[] for _ in range(N)]
visited = [0]*N
visited[0],visited[N-1] = 1,1
visited_all = [1]*N
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
nextA,nextB = G[0],G[N-1]
scoreA,scoreB = 1,1
while visited != visited_all:
    l = []
    for a in nextA:
        if visited[a] == 0:
            visited[a] = 1
            scoreA += 1
            for x in G[a]:
                l.append(x)
    nextA = l
    l = []
    for b in nextB:
        if visited[b] == 0:
            visited[b] = 1
            scoreB += 1
            for x in G[b]:
                l.append(x)
    nextB = l
print("Fennec" if scoreA > scoreB else "Snuke")

Solution (Python):
from collections import deque

N = int(input())
tree = {i: [] 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)

black_distance = {i: float('inf') for i in range(N+1)}
black_distance[1] = 0
white_distance = {i: float('inf') for i in range(N+1)}
white_distance[N] = 0


def bfs(start, distance):
    visited = set()
    que = deque()
    que.append(start)
    cnt = 0
    while que:
        now = que.popleft()
        nodes = tree[now]
        for n in nodes:
            if n not in visited:
                visited.add(n)
                distance[n] = min(distance[now] + 1, distance[n])
                que.append(n)
    return distance


black = bfs(1, black_distance)
white = bfs(N, white_distance)

black_cnt = 0
white_cnt = 0
for i in range(1, N+1):
    if black[i] <= white[i]:
        black_cnt += 1
    else:
        white_cnt += 1

if black_cnt > white_cnt:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
def d_fennec_vs_snuke(N, E):  
    
    edge = [[] for _ in range(N)]
    for a, b in E:
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)

    
    def bfs(N, adjacent, V):
        
        dist = [0 for i in range(N)]  
        isVisit = [False for i in range(N)]  
        queue = [V - 1]  
        isVisit[V - 1] = True

        while queue:
            u = queue.pop()
            for p in adjacent[u]:
                if not isVisit[p]:
                    isVisit[p] = True
                    dist[p] = dist[u] + 1
                    queue.append(p)
        return dist

    fennec_dist = bfs(N, edge, 1)  
    snuke_dist = bfs(N, edge, N)  
    fennec_point, snuke_point = 0, 0  

    for idx in range(N):
        if fennec_dist[idx] <= snuke_dist[idx]:
            fennec_point += 1
        else:
            snuke_point += 1
    if fennec_point > snuke_point:
        return 'Fennec'
    else:
        return 'Snuke'
    return None
N = int(input())
E = [[int(i) for i in input().split()] for j in range(N-1)]
print(d_fennec_vs_snuke(N, E))

Solution (Python):

"""
http://abc067.contest.atcoder.jp/tasks/arc078_b

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


def prepare_graph(edges, N):
    adj = [[] for _ in range(N+1)]
    for a, b in edges:
        adj[a].append([b, 1])
        adj[b].append([a, 1])
    return adj


def dijkstra(adj, s):
    
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(adj)
    d = [float('inf')] * len(adj)    
    d[s] = 0                    
    pq = []
    heappush(pq, (0, s))
    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue
        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d                    


def solve(edges, N):
    adj = prepare_graph(edges, N)
    f_dist = dijkstra(adj, 1)
    s_dist = dijkstra(adj, N)

    f_point = 0
    s_point = 0
    for f, s in zip(f_dist[1:], s_dist[1:]):
        if f <= s:
            f_point += 1
        else:
            s_point += 1
    if f_point > s_point:
        return 'Fennec'
    else:
        return 'Snuke'


def main(args):
    edges = []
    N = int(input())
    for _ in range(1, N):
        a, b = map(int, input().split())
        edges.append([a, b])
    ans = solve(edges, N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
n = int(input())
a=[[] for i in range(n)]
for i in range(n-1):
    b=[int(j)-1 for j in input().split()]
    a[b[0]].append(b[1])
    a[b[1]].append(b[0])
def dfs(v):
    d=[-1 for i in range(n)]
    q=[]
    d[v]=0
    q.append(v)
    while len(q):
        v=q.pop()
        for i in a[v]:
            if d[i]==-1:
                d[i]=d[v]+1
                q.append(i)
    return d
c1=dfs(0)
c2=dfs(n-1)
c=0
for i in range(n):
    if c1[i]>c2[i]:
        c+=1
if c>=n/2:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
n = int(input())

E = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    e = E.get(a, None)
    if e is None:
        e = []
    e.append(b)
    E[a] = e
    e = E.get(b, None)
    if e is None:
        e = []
    e.append(a)
    E[b] = e

xs = [0] * (n+1)



from collections import deque
q = deque()
q.append((1, 1))
q.append((n, -1))

while q:
    i, color = q.popleft()
    if xs[i] == 0:
        xs[i] = color
        e = E.get(i, None)
        if e:
            for j in e:
                q.append((j, color))
    else:
        continue

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

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

def path(s,g):
    visited = [0] * N
    back = [-1] * N
    stack = [(s,-1)]
    while stack:
        a,prev = stack.pop()
        visited[a] = 1
        back[a] = prev
        for to in es[a]:
            if visited[to]: continue
            if to == g:
                ret = [g,a]
                while back[ret[-1]] >= 0:
                    ret.append(back[ret[-1]])
                return list(reversed(ret))
            stack.append((to,a))

def fennec_win():
    win_border = (N//2)+1
    p = path(0,N-1)
    cant_go = p[(len(p)+1)//2]
    visited = [0] * N
    stack = [0]
    count = 0
    while stack:
        a = stack.pop()
        visited[a] = 1
        count += 1
        if count >= win_border:
            return True
        for to in es[a]:
            if visited[to] or to == cant_go: continue
            stack.append(to)
    return False

print('Fennec' if fennec_win() else 'Snuke')

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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



def dfs(now, cost, dic):
  dic[now] = cost
  for nx in adj[now]:
    if nx not in dic:
      dfs(nx, cost+1, dic)

dist_f = {}
dist_s = {}

dfs(0, 0, dist_f)
dfs(N-1, 0, dist_s)


f_cnt = 0
for  i in range(N):
  if dist_f[i] <= dist_s[i]:
    f_cnt += 1

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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



def dfs(now, cost, dic):
  dic[now] = cost
  for nx in adj[now]:
    if nx not in dic:
      dfs(nx, cost+1, dic)

dist_f = {}
dist_s = {}

dfs(0, 0, dist_f)
dfs(N-1, 0, dist_s)


f_cnt = 0
for  i in range(N):
  if dist_f[i] <= dist_s[i]:
    f_cnt += 1

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

Solution (Python):
N = int(input())

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

def calc_dist(K):
    
    dist = [-1 for i in range(N)]
    dist[-K] = 0

    
    from collections import deque
    stack = deque()
    stack.append(K)

    while stack:
        v = stack.pop()
        for nxt in adj[-v]:
            if dist[-nxt] == -1:
                dist[-nxt] = dist[-v] + 1
                stack.append(nxt)

    return dist

dist1 = calc_dist(1)
distN = calc_dist(N)

Fennec = 0
Snuke = 0
for v in range(N):
    if dist1[-v] <= distN[-v]:
        Fennec += 1
    else:
        Snuke += 1

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

Solution (Python):
import sys
sys.setrecursionlimit(sys.getrecursionlimit()*1000)

input = sys.stdin.readline
N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int,input().split())
    tree[a].append((b,1))
    tree[b].append((a,1))

depth = [None]*(N+1)
def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
DFS(1,0,0)

depthN = [None]*(N+1)
def DFSN(v,p,d):
    depthN[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFSN(e[0], v, d + e[1])
DFSN(N,0,0)

black = 0
for i in range(1,N):
    if depth[i] <= depthN[i]:
        black += 1

if black > N/2:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
def BFS(i,A,N):
  dist=[0]*N
  d=[-1]*N
  d[i]=0
  que=[i]
  dist=1
  while que:
    for j in range(len(que)):
      label=que.pop(0)
      for i in range(len(A[label])):
        if d[A[label][i]]==-1:
          d[A[label][i]]=dist
          que+=[A[label][i]]
    dist+=1
  return(d)

N=int(input())
ab=[]
for i in range(N-1):
  ab.append(list(map(int, input().split())))
A=[ [] for i in range(N) ]
for i in range(N-1):
  A[ab[i][0]-1]+=[ab[i][1]-1]
  A[ab[i][1]-1]+=[ab[i][0]-1]
 
 
dist1=BFS(0,A,N)
dist2=BFS(N-1,A,N)
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")

Solution (Python):
def BFS(i,A):
  dist=[0]*N
  d=[-1]*N
  d[i]=0
  que=[i]
  dist=1
  while que:
    for j in range(len(que)):
      label=que.pop(0)
      for i in range(len(A[label])):
        if d[A[label][i]]==-1:
          d[A[label][i]]=dist
          que+=[A[label][i]]
    dist+=1
  return(d)

N=int(input())
ab=[]
for i in range(N-1):
  ab.append(list(map(int, input().split())))
A=[ [] for i in range(N) ]
for i in range(N-1):
  A[ab[i][0]-1]+=[ab[i][1]-1]
  A[ab[i][1]-1]+=[ab[i][0]-1]
 
 
dist1=BFS(0,A)
dist2=BFS(N-1,A)
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")

Solution (Python):
N=int(input())
ab=[]
for i in range(N-1):
  ab.append(list(map(int, input().split())))
A=[ [] for i in range(N) ]
for i in range(N-1):
  A[ab[i][0]-1]+=[ab[i][1]-1]
  A[ab[i][1]-1]+=[ab[i][0]-1]
 
def BFS(i,A):
  dist=[0]*N
  d=[-1]*N
  d[i]=0
  que=[i]
  dist=1
  while que:
    for j in range(len(que)):
      label=que.pop(0)
      for i in range(len(A[label])):
        if d[A[label][i]]==-1:
          d[A[label][i]]=dist
          que+=[A[label][i]]
    dist+=1
  return(d)
 
dist1=BFS(0,A)
dist2=BFS(N-1,A)
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")

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

def BFS(i,A):
  dist=[0]*N
  d=[-1]*N
  d[i]=0
  que=[i]
  dist=1
  while que:
    for j in range(len(que)):
      label=que.pop(0)
      for i in range(len(A[label])):
        if d[A[label][i]]==-1:
          d[A[label][i]]=dist
          que+=[A[label][i]]
    dist+=1
  return(d)

dist1=BFS(0,A)
dist2=BFS(N-1,A)
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")

Solution (Python):
def Q4(x):
    N = x[0][0]
    edge = x[1:][:]

    
    adjacent = [0] * N
    for idx in range(N):
        adjacent[idx] = []
    for idx in range(N - 1):
        tmp = edge[idx][:]
        a = int(tmp[0]) - 1
        b = int(tmp[1]) - 1
        adjacent[a].append(b)
        adjacent[b].append(a)

    
    def bfs(N, adjacent, V):
        
        dist = [0 for i in range(N)]  
        isVisit = [False for i in range(N)]  
        queue = [V - 1]  
        isVisit[V - 1] = True

        while queue:
            u = queue.pop()
            for p in adjacent[u]:
                if not isVisit[p]:
                    isVisit[p] = True
                    dist[p] = dist[u] + 1
                    queue.append(p)
        return dist

    Fennec_dist = bfs(N, adjacent, 1)  
    Snuke_dist = bfs(N, adjacent, N)  
    Fennec_point, Snuke_point = 0, 0  

    for idx in range(N):
        if Fennec_dist[idx] <= Snuke_dist[idx]:
            Fennec_point += 1
        else:
            Snuke_point += 1
    if Fennec_point > Snuke_point:
        return 'Fennec'
    else:
        return 'Snuke'

import sys
n = int(input())
l = sys.stdin.readlines()
for idx in range(len(l)):
    l[idx] = l[idx].split()
    l[idx] = list(map(int, l[idx]))
lst = [[n]] + l
print(Q4(lst))

Solution (Python):
from collections import deque
EMPTY = 0
BLACK = 1
WHITE = 2
N = input()
G = {i: [] for i in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, raw_input().split())
    G[a].append(b)
    G[b].append(a)

parent = {}
dist = [N] * (N+1)
dist[1] = 0
que = deque([1])
while len(que) > 0:
    s = que.popleft()
    for t in G[s]:
        if dist[t] > dist[s]+1:
            dist[t] = dist[s]+1
            parent[t] = s
            que.append(t)

s = N
path = [s]
while s in parent:
    path.append(parent[s])
    s = parent[s]
path = path[::-1]

colors = [EMPTY] * (N+1)
n = len(path)
que_black, que_white = deque(), deque()
for i in range(n):
    if i % 2 == 0:
        v = path[i/2]
        colors[v] = BLACK
        que_black.append(v)
    else:
        v = path[n-i/2-1]
        colors[v] = WHITE
        que_white.append(v)

def paint(que, c):
    while len(que) > 0:
        s = que.popleft()
        for t in G[s]:
            if colors[t] == EMPTY:        
                colors[t] = c
                que.append(t)
paint(que_black, BLACK)
paint(que_white, WHITE)
score = 0
for c in colors:
    if c == BLACK:
        score += 1
    elif c == WHITE:
        score -= 1
print "Fennec" if score > 0 else "Snuke"

Solution (Python):
EMPTY = 0
BLACK = 1
WHITE = 2
N = input()
G = {i: [] for i in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, raw_input().split())
    G[a].append(b)
    G[b].append(a)

parent = {}
dist = [N] * (N+1)
dist[1] = 0
que = [1]
while len(que) > 0:
    s = que.pop(0)
    for t in G[s]:
        if dist[t] > dist[s]+1:
            dist[t] = dist[s]+1
            parent[t] = s
            que.append(t)

s = N
path = [s]
while s in parent:
    path.append(parent[s])
    s = parent[s]
path = path[::-1]

colors = [EMPTY] * (N+1)
n = len(path)
que_black, que_white = [], []
for i in range(n):
    if i % 2 == 0:
        v = path[i/2]
        colors[v] = BLACK
        que_black.append(v)
    else:
        v = path[n-i/2-1]
        colors[v] = WHITE
        que_white.append(v)

def paint(que, c):
    while len(que) > 0:
        s = que.pop(0)
        for t in G[s]:
            if colors[t] == EMPTY:        
                colors[t] = c
                que.append(t)
paint(que_black, BLACK)
paint(que_white, WHITE)
score = 0
for c in colors:
    if c == BLACK:
        score += 1
    elif c == WHITE:
        score -= 1
print "Fennec" if score > 0 else "Snuke"

Solution (Python):
import collections
 
N = int(input())
 
g = collections.defaultdict(list)
 
for _ in range(N - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)
 
bw = collections.defaultdict(str)
 
bw[1] = 'b'
bw[N] = 'w'
 
q = collections.deque()
q.append(1)
q.append(N)
 
f = 0
s = 0
 
while True:
    if len(q) == 0:
        break
 
    t = q.popleft()
 
    if bw[t] == 'b':
        f += 1
    if bw[t] == 'w':
        s += 1
 
    for succ in g[t]:
        if bw[succ] == '':
            bw[succ] = bw[t]
            q.append(succ)
 
if f > s:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import numpy as np
N= int(raw_input())
edge_list = [[] for i in range(N+1)]
for i in range(N-1):
	x,y = list(map(int, raw_input().split()))
	edge_list[x].append(y)
	edge_list[y].append(x)

dist_1 = [0] * (N+1)
dist_7 = [0] * (N+1)
point_1 = []
point_1 = []
point_7 = []
used_edge_1 = []
used_edge_7 = []
for point in edge_list[1]:
	dist_1[point] = 1
	point_1.append(point)

for point in edge_list[N]:
	dist_7[point] = 1
	point_7.append(point)


while len(point_1) != 0:
	v = point_1.pop()
	for u in edge_list[v]:
		if dist_1[u] == 0:
			point_1.append(u)
			dist_1[u] = dist_1[v] + 1


while len(point_7) != 0:
	v = point_7.pop()
	for u in edge_list[v]:
		if dist_7[u] == 0:
			point_7.append(u)
			dist_7[u] = dist_7[v] + 1


total_point = 0
for point in range(2,N):
	if dist_1[point] <= dist_7[point]:
		total_point += 1

if total_point > (N-2 - total_point):
	print "Fennec"
else:
	print "Snuke"

Solution (Python):


from queue import Queue

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

def search(start):
    dist = [0 for i in range(N+1)]
    is_visit = [False for i in range(N+1)]
    is_visit[start] = True
    q = Queue()
    q.put(start)

    while not q.empty():
        v = q.get()
        for u in graph[v]:
            if not is_visit[u]:
                is_visit[u] = True
                q.put(u)
                dist[u] = dist[v] + 1
    return dist

win_f = 0
win_s = 0
for f, s in zip(search(1)[2:N], search(N)[2:N]):
    if f <= s:
        win_f += 1
    else:
        win_s += 1
print("Fennec" if win_f > win_s else "Snuke")

Solution (Python):


import sys

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


for i in range(N-1):
    x,y=list(map(int,raw_input().split()))
    adj[x].append(y)
    adj[y].append(x)




F=(N+1)*[0]


S=[]


dist=(N+1)*[0]



S.append(1)
while len(S) != 0:
	
	v=S.pop()
	
	
	if F[v]==0:
		F[v]=1
		
		for u in adj[v]:
			
			if F[u]==0:
				S.append(u)
				dist[u]=dist[v]+1
				






F=(N+1)*[0]


S=[]


dist2=(N+1)*[0]


S.append(N)
while len(S) != 0:
	
	v=S.pop()
	
	
	if F[v]==0:
		F[v]=1
		
		for u in adj[v]:
			
			if F[u]==0:
				S.append(u)
				dist2[u]=dist2[v]+1
				





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


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

Solution (Python):


N=int(input())
moti=list(range(0,N,1))


for idx in range(0,N,1):
    moti[idx]=[]


for idx in range(0,N-1,1):
    mozir=input()
    hyo=mozir.split(' ')
    a=int(hyo[0])-1
    b=int(hyo[1])-1

    moti[a].append(b)
    moti[b].append(a)



belong=list(range(0,N,1))
for idx in range(0,N,1):
    belong[idx]=None

belong[0]="F"
belong[N-1]="S"

fennec_watch=[0]
sunuke_watch=[N-1]
fennec_haven=1
sunuke_haven=1
fennec_zou=1 
sunuke_zou=1 
Teban="F"
while True:
    if Teban=="F":
        fennec_next=[]
        for mono in fennec_watch:
            kouho=moti[mono]
            for butu in kouho:
                if belong[butu]==None:
                    fennec_next.append(butu)
                    belong[butu]="F"

        fennec_watch=fennec_next
        fennec_zou=len(fennec_next)
        fennec_haven=fennec_haven+fennec_zou
    else:
        sunuke_next=[]
        for mono in sunuke_watch:
            kouho=moti[mono]
            for butu in kouho:
                if belong[butu]==None:
                    sunuke_next.append(butu)
                    belong[butu]="S"

        sunuke_watch=sunuke_next
        sunuke_zou=len(sunuke_next)
        sunuke_haven=sunuke_haven+sunuke_zou
        
    if fennec_zou==0 and sunuke_zou==0:
        break
    Teban='F' if Teban=='S' else 'S'



if fennec_haven > sunuke_haven:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import collections

n = int(input())

d = collections.defaultdict(list)

for _ in range(n - 1):
    u, v = map(int, input().split())
    d[u].append(v)
    d[v].append(u)

bw = collections.defaultdict(str)

bw[1] = 'b'
bw[n] = 'w'

q = collections.deque()
q.append(1)
q.append(n)

fennec = 0
snuke = 0

while True:
    if len(q) == 0:
        break

    t = q.popleft()

    if bw[t] == 'b':
        fennec += 1
    if bw[t] == 'w':
        snuke += 1

    for succ in d[t]:
        if bw[succ] == '':
            bw[succ] = bw[t]
            q.append(succ)

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

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

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

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

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

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

cs=countson(k)
cf=n-cs

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

Solution (Python):
n=input()
ed=[[] for i in range(n+1)]
for i in range(n-1):
    c,d=map(int,raw_input().split())
    ed[c].append(d)
    ed[d].append(c)
a=[0 for i in range(n+1)]
b=[0 for j in range(n+1)]
visited=[0 for i in range(n+1)]
k=[1]
a[1]=1
visited[1]=1
while k!=[]:
    m=k.pop()
    for i in range(len(ed[m])):
        if visited[ed[m][i]]==0:
            k.append(ed[m][i])
            a[ed[m][i]]=a[m]+1
            visited[ed[m][i]]=1
k=[n]
b[n]=1
visited=[0 for i in range(n+1)]
visited[n]=1
while k!=[]:
    m=k.pop()
    for i in range(len(ed[m])):
        if visited[ed[m][i]]==0:
            k.append(ed[m][i])
            b[ed[m][i]]=b[m]+1
            visited[ed[m][i]]=1
cnt1=0
cnt2=0
for i in range(1,n+1):
    if a[i]<=b[i]: cnt1=cnt1+1
    if a[i]>b[i]: cnt2=cnt2+1
print "Fennec" if cnt1>cnt2 else "Snuke"

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

Solution (Python):
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_+1)//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")