Problem:


Score : 400 points

Problem Statement

Fennec and Snuke are playing a board game.

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

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

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

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

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

Constraints

2 \leq N \leq 10^5

1 \leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

Fennec

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

Sample Input 2

4
1 4
4 2
2 3

Sample Output 2

Snuke



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


Sample output:
Fennec

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())

path = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = ai_()
    path[a].append(b)
    path[b].append(a)

from collections import deque
q = deque()
q.append(0)

d1 = [float('inf') for _ in range(n)]
d1[0] = 0
w = set()
while q:
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            d1[vv] = d1[v] + 1
            q.append(vv)


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

dn = [float('inf') for _ in range(n)]
dn[n-1] = 0
w = set()
while q:
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            dn[vv] = dn[v] + 1
            q.append(vv)


d = [1 if d1[v] >= dn[v] else 0 for v in range(n)]

if d.count(1) > d.count(0):
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())

path = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = ai_()
    path[a].append(b)
    path[b].append(a)

from collections import deque
q = deque()
q.append(0)

d1 = [float('inf') for _ in range(n)]
d1[0] = 0
c = 0
w = set()
while q:
    c += 1
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            d1[vv] = c
            q.append(vv)


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

dn = [float('inf') for _ in range(n)]
dn[n-1] = 0
c = 0
w = set()
while q:
    c += 1
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            dn[vv] = c
            q.append(vv)


d = [1 if d1[v] >= dn[v] else 0 for v in range(n)]

if d.count(1) > d.count(0):
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())

path = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = ai_()
    path[a].append(b)
    path[b].append(a)

from collections import deque
q = deque()
q.append(0)

d1 = [float('inf') for _ in range(n)]
d1[0] = 0
c = 0
w = set()
while q:
    c += 1
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            d1[vv] = c
            q.append(vv)


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

dn = [float('inf') for _ in range(n)]
dn[n-1] = 0
c = 0
w = set()
while q:
    c += 1
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            dn[vv] = c
            q.append(vv)


print(d1,dn)
d = [1 if d1[v] >= dn[v] else 0 for v in range(n)]

if d.count(1) > d.count(0):
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1 << 30)

N = read()
edges = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = reads()
  a, b = a-1, b-1
  edges[a].append(b)
  edges[b].append(a)

def dist(u, d):
  for v in edges[u]:
    if d[v] >= 0:
      continue
    d[v] = d[u] + 1
    dist(v, d)
  return d

distf = dist(0, [0]+[-1]*(N-1))
dists = dist(N-1, [-1]*(N-1)+[0])

numf = sum(distf[i] <= dists[i] for i in range(N))
nums = N - numf

if numf >= nums:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(start, goal):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        if label not in visited:
            visited.append(label)
            if label == goal:
                return

            for v in d[label]:
                #if v not in visited:
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

n = int(input())
d = {i: [] for i in range(n)}

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

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[0] = 0
bfs(0, n - 1)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[-1] = 0
bfs(n - 1, 0)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] == float("inf"):
        Snuke += 1
    elif tekazu_Snuke[i] == float("inf"):
        Fennec += 1
    elif tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

#print(tekazu_Fennec, tekazu_Snuke)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(start, goal):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        if label not in visited:
            visited.append(label)
            if label == goal:
                return

            for v in d[label]:
                #if v not in visited:
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

n = int(input())
d = {i: [] for i in range(n)}

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

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[0] = 0
bfs(0, n - 1)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[-1] = 0
bfs(n - 1, 0)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

#print(tekazu_Fennec, tekazu_Snuke)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2000000)
n = int(input())
p = []
for i in range(n-1):
    p.append(list(map(int, input().split()))+ [1])
l = [[] for i in range(n+1)]
for pi in p: 
    l[pi[0]].append([pi[0],pi[1]])
    l[pi[1]].append([pi[1],pi[0]])
kyo = [float("inf")]*(n+1)
kyo[1] = 0
memo = [0] * (n+1)
memo[1] = 1
ruto = []
def dfs(start,ruto):
  ruto.extend(l[start])
  memo[start] = 1
  while ruto:
    a = ruto.pop()
    if memo[a[1]] == 1:
      continue
    kyo[a[1]] = kyo[a[0]] + 1
    dfs(a[1],ruto)
  return
dfs(1,ruto)

nkyo = [float("inf")]*(n+1)
nkyo[n] = 0
memo = [0] * (n+1)
memo[n] = 1
ruto = []
def dfs(start,ruto):
  ruto.extend(l[start])
  memo[start] = 1
  while ruto:
    a = ruto.pop()
    if memo[a[1]] == 1:
      continue
    nkyo[a[1]] = nkyo[a[0]] + 1
    dfs(a[1],ruto)
  return
dfs(n,ruto)
iti = 0
nko = 0
for i in range(1,n+1):
  if kyo[i] <= nkyo[i]:
    iti += 1
  else:
    nko += 1
print(kyo,nkyo)
if iti <= nko:
  print("Snuke")
else:
  print("Fennec")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]

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

def bfs(v):
    q = []
    depth = [n]*n
    q.append(v)
    depth[v] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth

d1 = bfs(0)
d2 = bfs(n-1)

c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]

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

def bfs(v):
    q = []
    depth = [n]*n
    q.append(v)
    depth[v] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth

d1 = bfs(0)
d2 = bfs(n-1)

c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
print(c)
if 2*c > n:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]

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

def bfs(x):
    q = []
    depth = [n]*n
    q.append(x)
    depth[x] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth

d1 = bfs(0)
d2 = bfs(n-1)

c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
if 2*c >= n:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]

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

def bfs(x):
    q = []
    depth = [n]*n
    q.append(x)
    depth[x] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth

d1 = bfs(0)
d2 = bfs(n-1)

c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]

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

def bfs(x):
    q = []
    depth = [n]*n
    q.append(x)
    depth[x] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth

d1 = bfs(0)
d2 = bfs(n-1)

c = 0
for i in range(n):
    if d1[i] >= d2[i]:
        c += 1
if 2*c < n:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]

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

def bfs(x):
    q = []
    depth = [n]*n
    q.append(x)
    depth[x] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth

d1 = bfs(0)
d2 = bfs(n-1)

c = 0
for i in range(n):
    if d1[i] > d2[i]:
        c += 1
if 2*c < n:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]

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

q = []
depth1 = [n]*n
q.append(0)
depth1[0] = 0
i = 0
while i < len(q):
    x = q[i]
    d = depth1[x]
    for e in edges[x]:
        if depth1[e] == n:
            depth1[e] = d+1
            q.append(e)
    i += 1

q = []
depth2 = [n]*n
q.append(n-1)
depth2[n-1] = 0
i = 0
while i < len(q):
    x = q[i]
    d = depth2[x]
    for e in edges[x]:
        if depth2[e] == n:
            depth2[e] = d+1
            q.append(e)
    i += 1

c = 0
for i in range(n):
    if depth1[i] > depth2[i]:
        c += 1
if 2*c < n:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
root = [[] for i in range(n+1)]
leaf = [0]*(n+1)
leaf[0] = -1
leaf[1] = 1
leaf[-1] = 2

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

turn = 1
while 0 in leaf:
    for idx, i in enumerate(leaf):
        if i == turn:
            for t in root[idx]:
                if leaf[t] == 0:
                    leaf[t] = turn
    if turn == 1: turn = 2
    else : turn = 1
    
if leaf.count(1) > int(n/2):
    print('Fennec')
else :
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n = int(input())
root = [[] for i in range(n+1)]
leaf = [0]*(n+1)
leaf[0] = -1
leaf[1] = 1
leaf[-1] = 2

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

turn = 1
while 0 in leaf:
    for idx, i in enumerate(leaf):
        if i == turn:
            for t in root[idx]:
                if leaf[t] == 0:
                    leaf[t] = turn
    print(leaf)
    if turn == 1: turn = 2
    else : turn = 1
    
if leaf.count(1) > int(n/2):
    print('Fennec')
else :
    print('Snuke')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#import sys
N=int(input())

edge=[[] for i in range(N)]

for i in range(N-1):
        a,b=[int(j)-1 for j in input().split()]
        edge[a].append(b)
        edge[b].append(a)
#入力終了

step=[999999999 for i in range(N)]

def paint(here,dist):
        step[here]=dist
        for to in edge[here]:
                if step[to]>dist+1:
                        paint(to,dist+1)
print("Snuke")

Submission status: Wrong Answer

Solution code:
def bfs(n, links):
    painted = set()
    fq = {0}
    sq = {n - 1}
    fs, ss = 0, 0
    while True:
        nfq, nsq = set(), set()
        for v in fq:
            nfq = links[v] - painted
            fs += len(nfq)
            painted.update(nfq)
            nfq.update(nfq)
        fq = nfq
        for v in sq:
            nsq = links[v] - painted
            ss += len(nsq)
            painted.update(nsq)
            nsq.update(nsq)
        sq = nsq
        if not fq:
            ss = n - fs
            break
        if not sq:
            fs = n - ss
            break
    return fs > ss


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('Fennec' if bfs(n, links) else 'Snuke')

Submission status: Wrong Answer

Solution code:
def bfs(n, links):
    painted = set()
    fq = {0}
    sq = {n - 1}
    fs, ss = 0, 0
    while len(painted) < n:
        for v in fq:
            nfq = links[v] - painted
            fs += len(nfq)
            painted.update(nfq)
            fq = nfq
        for v in sq:
            nsq = links[v] - painted
            ss += len(nsq)
            painted.update(nsq)
            sq = nsq
    return fs > ss


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('Fennec' if bfs(n, links) else 'Snuke')

Submission status: Wrong Answer

Solution code:
#相手のパスを潰したい
# こちら側に来てほしくない場合,最短経路を潰すしか無い
# 最適を簡単に表せない A - B - C - D
#                EF-|   |-GH...
# のとき、A→EFとやっていると、Bを取られて死ぬ
# でもこれをいちいち計算できない
# 「相手のパスを潰す」、というのは、最短経路がより短いほうが勝つと考える?
# でも相手にパスが潰されるかどうかはわからない
# とりあえずやってみる
n = int(input())
INF = 10**6
graph = [[float("inf")]*n for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1][b -1] = 1
    graph[b - 1][a - 1] = 1

#ダイクストラで0, n-1からの最短距離を求める


import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))
d = Dijkstra()
#print(d.dijkstra(graph, start=0))
#print(d.dijkstra(graph, start=n-1))
print("Fennec" if sum(d.dijkstra(graph, start=0)) <= sum(d.dijkstra(graph, start=n-1)) else "Snuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
node = [[] for i in range(n)]

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

def dfs(v):
    dis = [10 ** 10] * n
    dis[v] = 0
    q = []
    q.append(v)

    while q:
        u = q.pop()
        for i in node[u]:
            if dis[i] > dis[u] + 1:
                dis[i] = dis[u] + 1
                q.append(i)

    return dis

d1 = dfs(0)
d2 = dfs(n - 1)

c = 0
for i in range(2, n - 1):
    if d1[i] <= d2[i]:
        c += 1

if c > (n - 2) // 2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
node = [[] for i in range(n)]

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

def dfs(v):
    dis = [10 ** 10] * n
    dis[v] = 0
    q = []
    q.append(v)

    while q:
        u = q.pop()
        for i in node[u]:
            if dis[i] == 10 ** 10:
                dis[i] = dis[u] + 1
                q.append(i)

    return dis

d1 = dfs(0)
d2 = dfs(n - 1)

c = 0
for i in range(2, n - 1):
    if d1[i] <= d2[1]:
        c += 1

if c > (n - 2) // 2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
node = [[] for i in range(n)]

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

def dfs(v):
    dis = [10 ** 10] * n
    dis[v] = 0
    q = []
    q.append(v)

    while q:
        u = q.pop()
        for i in node[u]:
            if dis[i] > dis[u] + 1:
                dis[i] = dis[u] + 1
                q.append(i)

    return dis

d1 = dfs(0)
d2 = dfs(n - 1)

c = 0
for i in range(2, n - 1):
    if d1[i] <= d2[1]:
        c += 1

if c > (n - 2) // 2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import random

N = int(input())
nodes = [[] for i in range(N)]
edges = [list(map(int, input().split())) for i in range(N-1)]
color = [0 for i in range(N)]
color[0] = 1
color[N-1] = 2

for edge in edges:
    nodes[edge[0]-1].append(edge[1])
    nodes[edge[1]-1].append(edge[0])

fen = 0
snu = N-1

while True:
    try:
        if nodes[fen]!=[]:
            n = random.choice(nodes[fen]) - 1
            while color[n]!=0 and node[fen]!=[]:
                nodes[fen].remove(n)
                n = random.choice(nodes[fen]) - 1
            fen = n
            color[fen] = 1
    except:
        print('Snuke')
        break
    try:
        if nodes[snu]!=[]:
            n = random.choice(nodes[snu]) - 1
            while color[n]!=0 and node[snu]!=[]:
                nodes[snu].remove(n)
                n = random.choice(nodes[snu]) - 1
            snu = n
            color[fen] = 1
    except:
        print('Fennec')
        break

Submission status: Wrong Answer

Solution code:
def black(now):
    nextb=[]
    while now:
        a=now.pop()
        while desn[a]:
            go=desn[a].pop()
            if nodes[go]=='N':
                nodes[go]='B'
                nextb.append(go)
    return nextb

def white(now):
    nextb=[]
    while now:
        a=now.pop()
        while desn[a]:
            go=desn[a].pop()
            if nodes[go]=='N':
                nodes[go]='W'
                nextb.append(go)
    return nextb

n = int(input())
nodes=[]
desn=[]
for i in range(0,n+1):
    nodes.append("N")
    desn.append([])
nodes[1]='B'
nodes[n]='W'
for i in range(0,n-1):
    b, c = (int(i) for i in input().split())
    desn[b].append(c)
    desn[c].append(b)

nowb=[1]
noww=[n]
while nowb or noww:
    nowb=black(nowb)
    noww=white(noww)

b=nodes.count('B')
w=nodes.count('W')
if b>w:
    print('Fennec')
else:
    print('Sunuke')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class mas_node():
    def __init__(self, now_number, pass_route):
        self.now_number = now_number
        self.pass_route = pass_route
        self.pass_route.append(now_number)

    def set_now_number(self, now_number):
        self.now_number = now_number
        self.pass_route.append(now_number)

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]

    adj_list = {}
    for i in range(N):
        adj_list[i + 1] = []

    for i in range(N - 1):
        input_raw = list(read_func().strip().split())
        adj_list[int(input_raw[0])].append(int(input_raw[1]))
        adj_list[int(input_raw[1])].append(int(input_raw[0]))


    node_list = [mas_node(1, [])]
    is_already_pass = [False] * N
    is_already_pass[0] = True
    while 1:
        new_node_list = []
        for m_node in node_list:
            for next_mass_number in adj_list[m_node.now_number]:
                if is_already_pass[next_mass_number - 1] == False:
                    new_m_node = copy.deepcopy(m_node)
                    new_m_node.set_now_number(next_mass_number)
                    new_node_list.append(new_m_node)
                    is_already_pass[next_mass_number - 1] = True;
                    if next_mass_number == N:
                        one_to_N_pass = copy.deepcopy(new_m_node)
        node_list = copy.deepcopy(new_node_list)
        if new_node_list == []:
            break;
    to_N_pass_route = deque(one_to_N_pass.pass_route)
    to_N_pass_route.popleft()
    to_N_pass_route.pop()
    already_colored_list = [False] * N
    mas_set = {}
    mas_set["b"] = [1]
    mas_set["w"] = [N]
    pass_len = len(to_N_pass_route)
    for i in range(pass_len):
        if len(to_N_pass_route) == 0:
            break;
        b = to_N_pass_route.popleft()
        already_colored_list[b - 1] = True
        mas_set["b"].append(b)
        if len(to_N_pass_route) == 0:
            break;
        w = to_N_pass_route.popleft()
        already_colored_list[w - 1] = True
        mas_set["w"].append(w)

    black_mas_node = copy.deepcopy(mas_set["b"])
    white_mas_node = copy.deepcopy(mas_set["w"])
    while 1:
        new_black_mas_node = []
        for b_mas in black_mas_node:
            for next_b_mas in adj_list[b_mas]:
                if already_colored_list[next_b_mas - 1] == False:
                    mas_set['b'].append(next_b_mas)
                    new_black_mas_node.append(next_b_mas)
                    already_colored_list[next_b_mas - 1] = True
        black_mas_node = copy.deepcopy(new_black_mas_node)

        new_white_mas_node = []
        for w_mas in white_mas_node:
            for next_w_mas in adj_list[w_mas]:
                if already_colored_list[next_w_mas - 1] == False:
                    mas_set['w'].append(next_w_mas)
                    new_white_mas_node.append(next_w_mas)
                    already_colored_list[next_w_mas - 1] = True
        white_mas_node = copy.deepcopy(new_white_mas_node)

        if len(white_mas_node) == 0 & len(black_mas_node) == 0:
            break;

    if len(mas_set['b']) > len(mas_set['w']):
        print "Fennec"
    else:
        print "Snuke"



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
f=lambda*z:map(int,raw_input().split())
d=lambda s:csgraph.dijkstra(csr_matrix(([1]*len(a),(a,b)),[n+1]*2),0,s)
n,=f()
a,b=zip(*map(f,[0]*~-n))
g=d(1)
h=d(n)
print 'Snuke'if sum(g[i]>h[i] for i in range(1,n+1))*2>n else'Fennec'

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
f=lambda*z:map(int,raw_input().split())
d=lambda s:csgraph.dijkstra(csr_matrix(([1]*len(a),(a,b)),[n+1]*2),0,s)
n,=f()
a,b=zip(*map(f,[0]*~-n))
g=d(1)
h=d(n)
print 'Snuke'if sum(g[i]>h[i] for i in range(n+1))*2>n else'Fennec'

Submission status: Wrong Answer

Solution code:
n = int(input())
graph = {i: [] for i in range(n)}
path = [tuple(input().split(' ')) for _ in range(n - 1)]
for a, b in path:
    graph[int(a) - 1].append(int(b) - 1)
    graph[int(b) - 1].append(int(a) - 1)

unchecked = [[i for i in range(n)], [i for i in range(n)]]
point = [0, 0]

def dfs(player, masu, level):
    unchecked[player].remove(masu)
    if player == 0 and masu == n - 1:
        point[0] -= (level - 1) // 2
        return
    elif player == 1 and masu == 0:
        point[1] -= level // 2
        return
    else:
        point[player] += 1
        children = [i for i in graph[masu] if i in unchecked[player]]
        for child in children:
            dfs(player, child, level + 1)

dfs(0, 0, 0)
dfs(1, n - 1, 0)

if point[0] > point[1]: print('Fennec')
else: print('Snuke')

Submission status: Wrong Answer

Solution code:

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist



N=int(input())

g=myGraph()
for i in range(N-1):
    a,b=list(map(int,input().split(" ")))
    g.add_edge([a,b],1)

b1=g.dijkstra(1)
b2=g.dijkstra(N)

count=0
for k in range(1,N+1):
    if b1[k]<=b2[k]:
        count+=1

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