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:
n = int(input())

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

f = [n for _ in range(n)]
s = [n for _ in range(n)]

f[0] = 0
after = [] + p[0]
before = set()
dist = 0
while 1:
    dist += 1
    check = 0
    temp = []
    for x in after:
        if f[x] == n:
            f[x] = dist
            temp += p[x]
            check = 1
    if check == 0:
        break
    t2 = set(temp) - before
    before = set(after)
    after = list(t2)

s[n - 1] = 0
after = [] + p[n - 1]
before = set()
dist = 0
while 1:
    dist += 1
    check = 0
    temp = []
    for x in after:
        if s[x] == n:
            s[x] = dist
            temp += p[x]
            check = 1
    if check == 0:
        break
    t2 = set(temp) - before
    before = set(after)
    after = list(t2)

score_f = 0
for i in range(n):
    if f[i] <= s[i]:
        score_f += 1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB):
    g = defaultdict(dict)
    for a, b in AB:
        g[a][b] = 1
        g[b][a] = 1

    f = 1
    s = N

    def df(v):
        d = {v: 0}
        q = [(v, 0)]
        while q:
            v, c = q.pop()
            for u in g[v]:
                if u not in d:
                    d[u] = c + 1
                    q.append((u, c+1))
        return d

    sd = df(s)
    fd = df(f)

    # print(fd)
    # print(sd)

    fc = 0
    sc = 0
    for i in range(2, N):
        if i == s or i == f:
            continue

        if sd[i] >= fd[i]:
            fc += 1
        elif sd[i] < fd[i]:
            sc += 1

    return 'Fennec' if fc > sc else 'Snuke'


def main():
    N = read_int()
    # N, M = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def d_fennec_vs_snuke(N, E):  # 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):
        # 木のある頂点Vからの距離を求める
        dist = [0 for i in range(N)]  # 頂点Vからの距離
        isVisit = [False for i in range(N)]  # ある頂点が探索済か
        queue = [V - 1]  # 幅探索用キュー(配列が0-indexedのため-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)  # フェネック(頂点1スタート)から各頂点の距離
    snuke_dist = bfs(N, edge, N)  # すぬけ(頂点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))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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                    #  始点から自身までの距離は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:])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
#xs[1] = 1 #black by Fennec, first to play
#xs[n] = -1 #white by Snuke, second to play

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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[-i]:頂点Kから頂点iまでの距離
    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')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def BFS(i,A,N):
  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)
      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")

Submission status: Accepted

Solution code:
def BFS(i,A):
  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)
      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")

Submission status: Accepted

Solution code:
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#未訪問ならd=-1,訪問済みならiからの距離
  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")

Submission status: Accepted

Solution code:
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#未訪問ならd=-1,訪問済みならiからの距離
  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")

Submission status: Accepted

Solution code:
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):
        # 木のある頂点Vからの距離を求める
        dist = [0 for i in range(N)]  # 頂点Vからの距離
        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)  # フェネック(頂点1スタート)から各頂点の距離
    Snuke_dist = bfs(N, adjacent, N)  # すぬけ(頂点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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

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

Submission status: Accepted

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

#print adj

#訪問判別フラグ
F=(N+1)*[0]

#Stack
S=[]

#距離
dist=(N+1)*[0]


#先頭から深さ優先探索
S.append(1)
while len(S) != 0:
	#print S
	v=S.pop()
	#print v
	
	if F[v]==0:
		F[v]=1
		#print F
		for u in adj[v]:
			#print "u::"+str(u)
			if F[u]==0:
				S.append(u)
				dist[u]=dist[v]+1
				#print S

#print dist



#訪問判別フラグ
F=(N+1)*[0]

#Stack
S=[]

#距離
dist2=(N+1)*[0]

#最後から深さ優先探索
S.append(N)
while len(S) != 0:
	#print S
	v=S.pop()
	#print v
	
	if F[v]==0:
		F[v]=1
		#print F
		for u in adj[v]:
			#print "u::"+str(u)
			if F[u]==0:
				S.append(u)
				dist2[u]=dist2[v]+1
				#print S

#print dist2



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'

Submission status: Accepted

Solution code:
#coding=UTF-8

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

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

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

#path 0 to N-1
#width serach
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 #for breaking cond
sunuke_zou=1 #also
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'

#when fennec_haven==sunuke_haven==k
#k+1 th turn fennec 33-4
if fennec_haven > sunuke_haven:
    print('Fennec')
else:
    print('Snuke')