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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Runtime Error

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

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

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

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

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


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


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


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

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

    #Node[0]からbfs
    bfs(Node[0])

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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



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

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

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

    def findRoot(self) -> 'node':
        if self.root == self.parent:
            return self.root
        else:
            self.root = self.parent.root.findRoot()
            return self.root


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


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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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



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

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

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

    def findRoot(self) -> 'node':
        if self.root == self.parent:
            return self.root
        else:
            self.root = self.parent.root.findRoot()
            return self.root


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


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

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

    #Node[0]からbfs
    reserved: Deque[node] = deque([Node[0]])
    seen: Set[node] = {Node[0]}
    while len(reserved) > 0:
        current_node = reserved.popleft()
        for next_node in current_node.connection:
            if next_node in seen:
                continue
            next_node.setParent(current_node)
            seen.add(next_node)
            reserved.append(next_node)

    #between:Node[0]とNode[N-1]の間にあるノード数
    between = Node[N-1].rank -1
    #sep:お互い陣地を取り合った時に衝突する点(先手側)
    sep = (between+1)//2
    path = makePath(Node[0], Node[N-1])
    #衝突点の結合を削除
    path[sep+1].parent = path[sep+1]
    #2分した木のノード数集計
    fennec, snuke = Counter([n.findRoot().id for n in Node]).values()
    #勝者判定
    print('Fennec' if fennec > snuke else 'Snuke')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq as hq
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,1))
    edges[b].append((a,1))
INF = float("inf")
d = [INF]*N
d[0] = 0
q = [(0,0)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, w in edges[i]:
        if d[j] > d[i]+w:
            d[j] = d[i]+w
            hq.heappush(q, (d[j], j))
def cnt(n,m):
    ret = 1
    for v,_ in edges[n]:
        if v != m and not visited[v]:
            visited[v] = True
            ret += cnt(v,m)
    return ret
visited = [False]*N
visited[0] = True
fnc = cnt(0,N-1)
visited = [False]*N
visited[N-1] = True
snk = cnt(N-1,0)
if d[N-1] % 2 == 0:
    snk -= 1
print("Fennec" if snk < fnc else "Snuke")

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    ad_ls[a-1].append(b-1)
    ad_ls[b-1].append(a-1)
# 最終的にsnukeがnの半分以上のマスを所有していればsnukeの勝ち

# まず、fennecからsnukeへのパスを求める
node_from = [-1] * n
time = [float('inf')] * n
q = deque()

q.append(0)
time[0] = 0

while q:
    now = q.popleft()
    for nex in ad_ls[now]:
        if time[nex] == float('inf'):
            time[nex] = time[now] + 1
            q.append(nex)
            node_from[nex] = now

n_snuke_nodes = time[n-1]//2
snuke_list = [0] * n_snuke_nodes
now = n-1
for i in range(n_snuke_nodes):
    snuke_list[i] = now
    now = node_from[now]
NG = node_from[now]

done = [0] * n
done[NG] = 1
for i in range(n_snuke_nodes):
    done[snuke_list[i]] = 1

# sunke_list内に既にあるノードと、node_fromの最後のすぬけの後のやつには遷移しない
def dfs(now):
    num = 1
    for nex in ad_ls[now]:
        if not done[nex]:
            num += dfs(nex)
    return num

snuke = 0
for node in snuke_list:
    snuke += dfs(node)
if snuke >= n//2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
ad_ls = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    ad_ls[a-1].append(b-1)
    ad_ls[b-1].append(a-1)
# 最終的にsnukeがnの半分以上のマスを所有していればsnukeの勝ち

# まず、fennecからsnukeへのパスを求める
node_from = [-1] * n
time = [float('inf')] * n
q = deque()

q.append(0)
time[0] = 0

while q:
    now = q.popleft()
    for nex in ad_ls[now]:
        if time[nex] == float('inf'):
            time[nex] = time[now] + 1
            q.append(nex)
            node_from[nex] = now

n_snuke_nodes = time[n-1]//2
snuke_list = [0] * n_snuke_nodes
now = n-1
for i in range(n_snuke_nodes):
    snuke_list[i] = now
    now = node_from[now]
NG = node_from[now]

done = [0] * n
done[NG] = 1
for i in range(n_snuke_nodes):
    done[snuke_list[i]] = 1

# sunke_list内に既にあるノードと、node_fromの最後のすぬけの後のやつには遷移しない
def dfs(now):
    num = 1
    for nex in ad_ls[now]:
        if not done[nex]:
            num += dfs(nex)
    return num

snuke = 0
for node in snuke_list:
    snuke += dfs(node)
if snuke >= n//2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
def input():
    return stdin.readline().strip()

#setrecursionlimit((10**5) * 2)

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

# root: 0
# edge1: parent→children
# edge2: child→parent
# tfに探索済かどうかを保存する
tf = [False] * n
tf[0] = True
edge1 = [[] for _ in range(n)]
edge2 = [-1] * n

def divide(i):
    for j in edge[i]:
        if tf[j]:
            continue
        else:
            tf[j] = True
            edge1[i].append(j)
            edge2[j] = i
            divide(j)

divide(0)

now = n - 1
l = [n-1]
while edge2[now] != -1:
    now = edge2[now]
    l.append(now)

root = l[len(l)//2 - 1]

def divide2(i):
    ans = 1
    for j in edge1[i]:
        ans += divide2(j)
    return ans

Snuke = divide2(root)
Fennec = n - Snuke

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

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        xの属する木の根を返す
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        x, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    edge = []
    for _ in range(N - 1):
        a, b = map(int, input().split())
        repn[a - 1].append(b - 1)
        repn[b - 1].append(a - 1)
        if a > b: a, b = b, a
        edge.append((a - 1, b - 1))

    """
    まさかの問題を読み間違えていた。。。
    （プレイヤーがマスの上を１マスずつ動くと思っていた）

    「最適に行動した時」＝「どちらかに必勝法が存在する」と言い換える。
    あとはその戦略を見出せば勝ち。見抜けなければ相手の全行動パターンに勝つ手の存在を示す。
    同じ色が隣接していればどのマスでも塗れるなら、最初に一気に２人が距離を詰めた方がいいに決まってる。
    """

    # 頂点０からのdepthを求める
    depth_from_0 = [-1] * N
    parent = [-1] * N
    leaf = []
    depth_from_0[0] = 0

    def dfs(u):
        cnt = 0
        for v in repn[u]:
            if depth_from_0[v] != -1: continue
            cnt += 1
            depth_from_0[v] = depth_from_0[u] + 1
            parent[v] = u
            dfs(v)
        if cnt == 0: leaf.append(u)

    dfs(0)

    # ２人を結ぶパスの同定
    path = [N - 1]
    while path[-1] != 0: path.append(parent[path[-1]])
    path.append(0)
    l = len(path)

    # ２人が互いに塗るマスの数を計算
    tree = UnionFind(N)
    a0, b0 = path[l // 2 - 1], path[l // 2]
    if a0 > b0: a0, b0 = b0, a0
    for a, b in edge:
        if a != a0 or b != b0: tree.union(a, b)
    Fennec = tree.size(0)
    Snuke = tree.size(N - 1)
    if Fennec > Snuke:
        print("Fennec")
    else:
        print("Snuke")



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
def f(x,q):
    for i in route[x]:
        if not visit[i]:
            visit[i] = True
            f(i,q+[i])
            visit[i] = False
            if i == n-1:
                p = q + [i-1]
                flag = True
                return p
n = int(input())
route = [[] for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x:int(x)-1,input().split())
    route[a].append(b)
    route[b].append(a)
visit = [False for i in range(n)]
p = f(0,[0])
t = p[-(-len(p)//2)-1]

d = deque()
d.append(n-1)
visit = [False for i in range(n)]
siro = 1
while d:
    now = d.popleft()
    for i in route[now]:
        if not visit[i] and i != t:
            visit[i] = True
            d.append(i)
            siro += 1
kuro = n - siro
if kuro <= siro:
    print("Snuke")
elif kuro > siro:
    print("Fennec")

Submission status: Runtime Error

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

ds = [-1]*n
n_l_total = [0]
def dfs(idx,s):
    ds[idx] = 1
    ret = None
    for i in g[idx]:
        if ds[i] == -1:
            s_tmp = s + ":" + str(i)
            if i == n-1:
                return s_tmp
            else:
                ret = dfs(i,s_tmp)
                if ret != None:
                    return ret
    else:
        if s.find(str(n-1)) == -1:
            n_l_total[0] += 1
    return ret

root = dfs(0,"0").split(':')
len_root = len(root)
n_r = len_root // 2
n_l = len_root - n_r
if n_l_total[0]+n_l > n // 2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

def main():
  n=int(input())
  edges=[tuple(map(int,input().split())) for _ in range(n-1)]
  d=defaultdict(list)
  for e in edges:
    d[e[0]].append(e[1])
    d[e[1]].append(e[0])
  def dist(m):
    dl=[-1]*(n+1)
    cv=deque([m])
    nv=deque([1])
    while nv:
      c+=1
      cv.extend(nv)
      nv.clear()
      for e in cv:
        dl[e]=c
        for x in d[e]:
          if dl[x]<0:
            nv.append(x)
      cv.clear()
    return dl[1:]
  fnc=dist(1)
  snk=dist(n)
  j=sum([(fnc[i]<=snk[i])-(fnc[i]>snk[i]) for i in range(n)])
  if j>0:
    print('Fennec')
  else:
    print('Snuke')

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import itertools
from collections import deque
n=int(input())
edge = [[] for _ in range(n)]
visited = [0]*n
for i in range(n-1):
    a,b=map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
path = []
def dfs(i):
    visited[i]=1
    if(i==n-1):
        return 1
    else:
        for j in edge[i]:
            if(not visited[j]):
                if(dfs(j)):
                    if(i!=0):
                        path.append(i)
                    return i

    return 0



dfs(0)
s = 0
f = 0
visited_new = [-1]*n
path_l = len(path)
for i in range(path_l):
    if(i<(path_l//2)):
        visited_new[path[i]]=1
        s+=1
    else:
        visited_new[path[i]]=2
        f+=1

visited_new[n-1]=3
visited_new[0]=3
que=deque()
que.append(n-1)
while que:
    v=que.popleft()
    for next_v in edge[v]:
        if visited_new[next_v]==2:continue
        if visited_new[next_v]==1 or visited_new[next_v]==-1:
            visited_new[next_v]=3
            que.append(next_v)
            s+=1
que.append(0)
while que:
    v=que.popleft()
    for next_v in edge[v]:
        if visited_new[next_v]==3:continue
        if visited_new[next_v]==2 or visited_new[next_v]==-1:
            visited_new[next_v]=3
            que.append(next_v)
            f+=1

if(f>=s):
    print("Fennec")
else:
    print("Snuke")

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
tree = [[] for _ in range(N)] #i行目には、i番目のマスと隣り合っているマスの番号が加えられる
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

color = [0] * N #色が塗られていなければ0、黒は1、白は-1
color[0] = 1
color[N-1] = -1
que = collections.depue() #色が塗られたマスの番号を、隣り合うマスが全て塗られるまでここに入れる
que.append(0)
que.append(N-1)
while que: #塗るべきマスがなくなるまで繰り返す
    i = que.popleft() #「左から」が重要 #n回でたどり着けるマスはn回目に全て塗って良い
    for x in tree[i]:
        if color[x] == 0:
            color[x] = color[i]
            que.append(x) #塗ったマスは調べるリストに入れる

if sum(color) > 0: #合計が正、つまり黒が多い場合は先手の勝ち
    print("Fennec")
else: #合計が0でも先手の塗るマスがないため後手の勝ち
    print("Snuke")

Submission status: Runtime Error

Solution code:
def dijkstra(s, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev


def main():
    from itertools import accumulate
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk = dijkstra(n, g)

    vis = [False] * (n + 1)

    def f(now, c):
        if vis[now]:
            return

        vis[now] = True
        c += 1
        for _, nxt in g[now]:
            f(nxt, c)

        return c

    nw = dk[1]

    cnt = []
    vis[1] = True
    vis[n] = True
    while nw != n:
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw, 0)
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    *a, = accumulate(cnt)
    l = len(a)
    k = l // 2 - 1 if l % 2 == 0 else l // 2
    fn += a[k] if l > 0 else 0
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

dist = [(0,-1) for _ in range(n)]
def dfs(now,prev=-1):
    for nxt in G[now]:
        if nxt == prev: continue
        dist[nxt] = (dist[now][0]+1,now)
        dfs(nxt,now)
dfs(0)

color = ["?"]*n
cnt = 0
now = n-1
w = (dist[n-1][0]+1)//2
while now != -1:
    if cnt < w: color[now] = -1
    else: color[now] = 1
    cnt += 1
    now = dist[now][1]

def coloring(now,prev=-1):
    for nxt in G[now]:
        if nxt == prev: continue
        if color[nxt] != "?" and color[now] != color[nxt]: continue
        color[nxt] = color[now]
        coloring(nxt,now)
coloring(0)
coloring(n-1)
print("Fennec" if sum(color) > 0 else "Snuke")

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
g = [ [] for i in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
visit = [0]*N
q=deque()
a = [0]*N
b = [0]*N
def tansakuf(i):
  visit[i] = 1
  for j in g[i]:
    if visit[j] == 0 and j != i:
      a[j] = a[i] + 1
      q.append(j)
  if len(q) != 0:
    x=q.popleft()
    return tansakuf(x)
tansakuf(0)
def tansakus(i):
  visit[i] = 0
  for j in g[i]:
    if visit[j] == 1 and j != i:
      b[j] = b[i] + 1
      q.append(j)
  if len(q) != 0:
    x=q.popleft()
    return tansakus(x)
tansakus(N-1)
cnt = 0
for i in range(N):
  if a[i] <= b[i]:
    cnt += 1
  else:
    cnt -= 1
if cnt > 0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
g = [ [] for i in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
visit = [0]*N
q=deque()
a = [0]*N
b = [0]*N
def tansakuf(i):
  visit[i] = 1
  for j in g[i]:
    if visit[j] == 0:
      a[j] = a[i] + 1
      q.append(j)
  if len(q) != 0:
    x=q.popleft()
    return tansakuf(x)
tansakuf(0)
def tansakus(i):
  visit[i] = 0
  for j in g[i]:
    if visit[j] == 1:
      b[j] = b[i] + 1
      q.append(j)
  if len(q) != 0:
    x=q.popleft()
    return tansakus(x)
tansakus(N-1)
cnt = 0
for i in range(N):
  if a[i] <= b[i]:
    cnt += 1
  else:
    cnt -= 1
if cnt > 0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
g = [ [] for i in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
visit = [0]*N
e = []
a = [0]*N
b = [0]*N
def tansakuf(i):
  visit[i] = 1
  for j in g[i]:
    if visit[j] == 0:
      a[j] = a[i] + 1
      e.append(j)
  if 0 in visit:
    f = e[0]
    e.pop(0)
    return tansakuf(f)
tansakuf(0)
def tansakus(i):
  visit[i] = 0
  for j in g[i]:
    if visit[j] == 1:
      b[j] = b[i] + 1
      e.append(j)
  if 1 in visit:
    f = e[0]
    e.pop(0)
    return tansakus(f)
tansakus(N-1)
cnt = 0
for i in range(N):
  if a[i] <= b[i]:
    cnt += 1
  else:
    cnt -= 1
if cnt > 0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Runtime Error

Solution code:
N = int(input())
g = [ [] for i in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
visit = [0]*N
e = []
a = [0]*N
b = [0]*N
def tansakuf(i):
  visit[i] = 1
  for j in g[i]:
    if visit[j] == 0:
      a[j] = a[i] + 1
      e.append(j)
  if len(e) != 0:
    f = e[0]
    e.pop(0)
    return tansakuf(f)
tansakuf(0)
def tansakus(i):
  visit[i] = 0
  for j in g[i]:
    if visit[j] == 1:
      b[j] = b[i] + 1
      e.append(j)
  if len(e) != 0:
    f = e[0]
    e.pop(0)
    return tansakus(f)
tansakus(N-1)
cnt = N
for i in range(N):
  if a[i] <= b[i]:
    cnt += 1
  else:
    cnt -= 1
if cnt > N:
  print('Fennec')
else:
  print('Snuke')

Submission status: Runtime Error

Solution code:
N = int(input())
g = [ [] for i in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
visit = [0]*N
e = []
a = [0]*N
b = [0]*N
def tansakuf(i):
  visit[i] = 1
  for j in g[i]:
    if visit[j] == 0:
      a[j] = a[i] + 1
      e.append(j)
  if len(e) != 0:
    f = e[0]
    e.pop(0)
    return tansakuf(f)
tansakuf(0)
def tansakus(i):
  visit[i] = 0
  for j in g[i]:
    if visit[j] == 1:
      b[j] = b[i] + 1
      e.append(j)
  if len(e) != 0:
    f = e[0]
    e.pop(0)
    return tansakus(f)
tansakus(N-1)
cnt = 0
for i in range(N):
  if a[i] <= b[i]:
    cnt += 1
  else:
    cnt -= 1
if cnt > 0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Runtime Error

Solution code:
N = int(input())
g = [ [] for i in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
visit = [0]*N
e = []
a = [0]*N
b = [0]*N
def tansakuf(i):
  visit[i] = 1
  for j in g[i]:
    if visit[j] == 0:
      a[j] = a[i] + 1
      e.append(j)
  if len(e) != 0:
    f = e[0]
    e.pop(0)
    return tansakuf(f)
tansakuf(0)
visit = [0]*N
def tansakus(i):
  visit[i] = 1
  for j in g[i]:
    if visit[j] == 0:
      b[j] = b[i] + 1
      e.append(j)
  if len(e) != 0:
    f = e[0]
    e.pop(0)
    return tansakus(f)
tansakus(N-1)
cnt = 0
for i in range(N):
  if a[i] <= b[i]:
    cnt += 1
  else:
    cnt -= 1
if cnt > 0:
  print('Fennec')
else:
  print('Snuke')