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:
import heapq


def dijkstra(s, g):
    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(x, c):
        if vis[x]:
            return 0

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

        return c

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

    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 else 0
    sn = n - fn

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq


def dijkstra(s, g):
    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(x, c):
        if vis[x]:
            return 0

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

        return c

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

    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 else 0
    sn = n - fn

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    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(j)
        g[j].append(i)

    q = deque([1])
    cnt = 0
    vis = [False] * (n + 1)
    while q:
        i = q.popleft()
        if i == n or vis[i]:
            continue

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

    print("Fennec" if cnt * 2 > n else "Sunuke")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    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(j)
        g[j].append(i)

    q = [1]
    cnt = 0
    vis = [False] * (n + 1)
    while q:
        i = q.pop()
        if i == n or vis[i]:
            continue

        vis[i] = True
        cnt += 1
        q = g[i] + q

    print("Fennec" if cnt * 2 > n else "Sunuke")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 木なので、任意の2点を結ぶルートはただ1つだけ存在する
# 最初にそこを順に埋めるのが最適。後は自分の陣営を埋めていく。
# 問題：点1→点Nのルートをどう求める? →幅優先探索かなぁ。

# 幅優先探索を2回やる必要がありそう
# 1回目で点1→点Nのルートを辿る。各点で1つ前の点をメモ。点Nから点1に逆にたどり、距離が半分の点Pを記録する
# 2回めでもう一度点1から辿る、点Pから先は探索しない（Snukeに取られる部分）。探索できた地点数が半分以上か否かを調べる

from collections import deque

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n-1)]

neighbor = [[] for i in range(n)]
for e in edges:
    neighbor[e[0] - 1].append(e[1] - 1)
    neighbor[e[1] - 1].append(e[0] - 1)
    # 1-index → 0-index

info = [(-1, -1)] * n
info[0] = (0, -1) # 点1からの距離, 1つ点1寄りの点の番号

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

# 1回目
while True:
    v = q.popleft()
    distance = info[v][0]
    for nei in neighbor[v]:
        if info[nei][0] < 0:
            q.append(nei)
            info[nei] = (distance + 1, v)
    if len(q) == 0:
        break

# print(info)

# 点1〜点Nの距離が 10の場合、先手は5まで行ける。11の場合、5まで行ける。
# 逆に辿る
now = n-1
distance = info[n-1][0]
half = distance // 2
while True:
    now = info[now][1]
    distance -= 1
    if distance == half:
        half_point = now
        break

info = [(-1, -1)] * n
info[0] = (0, -1) # 点1からの距離, 1つ点1寄りの点の番号

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

n_visited = 1
# 2回目

while True:
    v = q.popleft()
    distance = info[v][0]
    for nei in neighbor[v]:
        if info[nei][0] < 0 and v != half_point:
            q.append(nei)
            info[nei] = (distance + 1, v)
            n_visited += 1

    if len(q) == 0:
        break

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

Submission status: Wrong Answer

Solution code:
# 木なので、任意の2点を結ぶルートはただ1つだけ存在する
# 最初にそこを順に埋めるのが最適。後は自分の陣営を埋めていく。
# 問題：点1→点Nのルートをどう求める? →幅優先探索かなぁ。

# 幅優先探索を2回やる必要がありそう
# 1回目で点1→点Nのルートを辿る。各点で1つ前の点をメモ。点Nから点1に逆にたどり、距離が半分の点Pを記録する
# 2回めでもう一度点1から辿る、点Pから先は探索しない（Snukeに取られる部分）。探索できた地点数が半分以上か否かを調べる

from collections import deque

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n-1)]

neighbor = [[] for i in range(n)]
for e in edges:
    neighbor[e[0] - 1].append(e[1] - 1)
    neighbor[e[1] - 1].append(e[0] - 1)
    # 1-index → 0-index

info = [(-1, -1)] * n
info[0] = (0, -1) # 点1からの距離, 1つ点1寄りの点の番号

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

# 1回目
while True:
    v = q.popleft()
    distance = info[v][0]
    for nei in neighbor[v]:
        if info[nei][0] < 0:
            q.append(nei)
            info[nei] = (distance + 1, v)
    if len(q) == 0:
        break

# print(info)

# 点1〜点Nの距離が 10の場合、先手は5まで行ける。11の場合、5まで行ける。
# 逆に辿る
now = n-1
distance = info[n-1][0]
half = distance // 2
while True:
    now = info[now][1]
    distance -= 1
    if distance == half:
        half_point = now
        break

info = [(-1, -1)] * n
info[0] = (0, -1) # 点1からの距離, 1つ点1寄りの点の番号

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

n_visited = 1
# 2回目

while True:
    v = q.popleft()
    distance = info[v][0]
    for nei in neighbor[v]:
        if info[nei][0] < 0 and v != half_point:
            q.append(nei)
            info[nei] = (distance + 1, v)
            n_visited += 1

    if len(q) == 0:
        break

if n_visited >= (n+1) // 2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]
    adjlist = {}
    for a, b in AB:
        adjlist.setdefault(a-1, [])
        adjlist.setdefault(b-1, [])
        adjlist[a-1].append(b-1)
        adjlist[b-1].append(a-1)
    import collections
    q = collections.deque([[0, []]])
    shortest = None
    while q:
        v, path = q.popleft()
        path = path+[v]
        if v == N-1:
            shortest = set(path[1:-1])
            break
        for nxt in adjlist[v]:
            q.append([nxt, path])
    assert shortest is not None, "bfs error"
    
    # print(adjlist)
    # print(shortest)
    b_nexts = set(adjlist[0])
    w_nexts = set(adjlist[N-1])
    colored = [False for _ in range(N)]
    colored[0] = True
    colored[N-1] = True
    b_turn = True
    while all(colored) is False:
        if b_turn:
            if len(b_nexts) == 0:
                print("Snuke")
                return
            intsecs = b_nexts & shortest
            if len(intsecs) > 0:
                nxt = intsecs.pop()
                b_nexts.remove(nxt)
                shortest.remove(nxt)
            else:
                nxt = b_nexts.pop()
        else:
            if len(w_nexts) == 0:
                print("Fennec")
                return
            intsecs = w_nexts & shortest
            if len(intsecs) > 0:
                nxt = intsecs.pop()
                w_nexts.remove(nxt)
                shortest.remove(nxt)
            else:
                nxt = w_nexts.pop()

        colored[nxt] = True
        for v in adjlist[nxt]:
            if colored[v] is False:
                if b_turn:
                    b_nexts.add(v)
                else:
                    w_nexts.add(v)
        
        b_turn = not b_turn
    print("Snuke" if b_turn else "Fennec")


if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]
    adjlist = {}
    for a, b in AB:
        adjlist.setdefault(a-1, [])
        adjlist.setdefault(b-1, [])
        adjlist[a-1].append(b-1)
        adjlist[b-1].append(a-1)
    import collections
    q = collections.deque([[0, []]])
    shortest = None
    while q:
        v, path = q.popleft()
        path = path+[v]
        if v == N-1:
            shortest = set(path)
            break
        for nxt in adjlist[v]:
            q.append([nxt, path])
    assert shortest is not None, "bfs error"
    
    # print(adjlist)
    # print(shortest)
    b_nexts = set(adjlist[0])
    w_nexts = set(adjlist[N-1])
    colored = [False for _ in range(N)]
    colored[0] = True
    colored[N-1] = True
    b_turn = True
    while True:
        if b_turn:
            if len(b_nexts) == 0:
                print("Snuke")
                return
            intsecs = b_nexts & shortest
            if len(intsecs) > 0:
                nxt = intsecs.pop()
                b_nexts.discard(nxt)
                shortest.discard(nxt)
            else:
                nxt = b_nexts.pop()
        else:
            if len(w_nexts) == 0:
                print("Fennec")
                return
            intsecs = w_nexts & shortest
            if len(intsecs) > 0:
                nxt = intsecs.pop()
                w_nexts.discard(nxt)
                shortest.discard(nxt)
            else:
                nxt = w_nexts.pop()

        colored[nxt] = True
        for v in adjlist[nxt]:
            if colored[v] is False:
                if b_turn:
                    b_nexts.add(v)
                else:
                    w_nexts.add(v)
        
        b_turn = not b_turn


if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    E = []
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        G[b].append(a)
        E.append((a, b))
    par = [-1] * N
    par[0] = 0
    stk = [0]
    while stk:
        v = stk.pop()
        for to in G[v]:
            if par[to] >= 0:
                continue
            par[to] = v
            stk.append(to)
    path = []
    v = N - 1
    while v != 0:
        path.append(v)
        v = par[v]
    path.append(0)
    m = (len(path) - 1) // 2
    x, y = path[m], path[m - 1]
    uf = UnionFindTree(N)
    for a, b in E:
        if a == x and b == y or a == y and b == x:
            continue
        uf.union(a, b)
    print('Fennec' if uf.size(0) > uf.size(N - 1) else 'Snuke')

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    E = []
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        G[b].append(a)
        E.append((a, b))
    par = [-1] * N
    par[0] = 0
    stk = [0]
    while stk:
        v = stk.pop()
        for to in G[v]:
            if par[to] >= 0:
                continue
            par[to] = v
            stk.append(to)
    path = []
    v = N - 1
    while v != 0:
        path.append(v)
        v = par[v]
    path.append(0)
    m = (len(path) - 1) // 2
    x, y = path[m], path[m + 1]
    uf = UnionFindTree(N)
    for a, b in E:
        if a == x and b == y or a == y and b == x:
            continue
        uf.union(a, b)
    print('Fenec' if uf.size(0) > uf.size(N - 1) else 'Snuke')

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)
a = [-1]*N
b = [-1]*N
def bfs(n):
  q=deque()
  q.append(n)
  a[n] = 0
  while len(q):
    x=q.popleft()
    for i in g[x]:
      if a[i]==-1: 
        a[i]=a[x]+1
        q.append(i)
bfs(0)
def bfs2(n):
  q=deque()
  q.append(n)
  a[n] = 0
  while len(q):
    x=q.popleft()
    for i in g[x]:
      if b[i]==-1: 
        b[i]=b[x]+1
        q.append(i)
bfs2(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: Wrong Answer

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)
l = [0]*N
l[0] = 1
l[N-1] = -1
a = [0]
b = [N-1]
while 0 in l:
  for i in a:
    for j in g[i]:
      if l[j] == 0:
        a.append(j)
        l[j] = 1
    a.pop(0)
  for i in b:
    for j in g[i]:
      if l[j] == 0:
        b.append(j)
        l[j] = -1
    b.pop(0)
if sum(l) >= 0:
  print('Fennec')
else:
  print('Snuke')

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
f = 0
s = 0
from collections import deque
ps = [-1] * n
used = [False] * n
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    a = q.popleft()
    if a == n-1:
        break
    for u in edges[a]:
        if not used[u]:
            ps[u] = a
            q.append(u)
            used[u] = True

nx = n - 1
xs = [n-1]
while nx != 0:
    nx = ps[nx]
    xs.append(nx)

xs.reverse()
l = len(xs) - 2
f = (l+1)//2
s = l-f

if len(xs) == 2:
    z_lim = -1
    n_lim = 0
else:
    z_lim = len(xs)//2+1
    n_lim = len(xs)//2

# bfs 0側
used = [-1] * n
used[0] = 0 
q = deque([0])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[z_lim]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
f += cnt

# bfs n-1側
used = [-1] * n
used[n-1] = 0 
q = deque([n-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[n_lim]:
            q.append(u)
            used[u] = 0
            cnt += 1

s += cnt
# print("z_lim",z_lim,"nlim",n_lim)
# print("f",f,"s",s)
if f > s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
f = 0
s = 0
from collections import deque
ps = [-1] * n
used = [False] * n
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    a = q.popleft()
    if a == n-1:
        break
    for u in edges[a]:
        if not used[u]:
            ps[u] = a
            q.append(u)
            used[u] = True
nx = n - 1
xs = [n-1]
while nx != 0:
    nx = ps[nx]
    xs.append(nx)
l = len(xs) - 2
f = (l + 1)//2
s = l - f
mid = (len(xs)+1)//2 - 1
# bfs 0側
used = [-1] * n
used[0] = 0 
q = deque([0])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[mid+1]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
f += cnt

# bfs n-1側
used = [-1] * n
used[n-1] = 0 
q = deque([n-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[mid]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
s += cnt

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

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
f = 0
s = 0
from collections import deque
ps = [-1] * n
used = [False] * n
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    a = q.popleft()
    if a == n-1:
        break
    for u in edges[a]:
        if not used[u]:
            ps[u] = a
            q.append(u)
            used[u] = True
nx = n - 1
xs = [n-1]
while nx != 0:
    nx = ps[nx]
    xs.append(nx)
l = len(xs) - 2
f = (l + 1)//2
s = l - f
mid = (len(xs)+1)//2 - 1
# bfs 0側
used = [-1] * n
used[0] = 0 
q = deque([0])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[mid]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
f += cnt

# bfs n-1側
used = [-1] * n
used[n-1] = 0 
q = deque([n-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[mid+1]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
s += cnt

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

Submission status: Wrong Answer

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

f = 0
s = 0
from collections import deque
ps = [-1] * n
used = [False] * n
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    a = q.popleft()
    if a == n-1:
        break
    for u in edges[a]:
        if not used[u]:
            ps[u] = a
            q.append(u)
            used[u] = True

nx = n-1
xs = [n-1]
while nx != 0:
    nx = ps[nx]
    xs.append(nx)
l = len(xs) - 2

f = (l+1)//2
s = l-f

# bfs 0側
used = [-1] * n
used[0] = 0 
q = deque([0])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if l == 0:
            if used[u] == -1 and u != xs[1]:
                q.append(u)
                used[u] = 0
                cnt += 1

        else:
            if used[u] == -1 and u != xs[-2]:
                q.append(u)
                used[u] = 0
                cnt += 1
# print("cnt",cnt)
f += cnt

# bfs n-1側
used = [-1] * n
used[n-1] = 0 
q = deque([n-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if l == 0:
            if used[u] == -1 and u != xs[0]:
                q.append(u)
                used[u] = 0
                cnt += 1

        else:
            if used[u] == -1 and u != xs[1]:
                q.append(u)
                used[u] = 0
                cnt += 1

# print("cnt",cnt)
s += cnt

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

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
f = 0
s = 0
from collections import deque
ps = [-1] * n
used = [False] * n
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    a = q.popleft()
    if a == n-1:
        break
    for u in edges[a]:
        if not used[u]:
            ps[u] = a
            q.append(u)
            used[u] = True
nx = n - 1
xs = [n-1]
while nx != 0:
    nx = ps[nx]
    xs.append(nx)
l = len(xs) - 2

f = (l+1)//2
s = l-f

# bfs 0側
used = [-1] * n
used[0] = 0 
q = deque([0])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[-2]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
f += cnt

# bfs n-1側
used = [-1] * n
used[n-1] = 0 
q = deque([n-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[1]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
s += cnt

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

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
f = 0
s = 0
from collections import deque
ps = [-1] * n
used = [False] * n
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    a = q.popleft()
    if a == n-1:
        break
    for u in edges[a]:
        if not used[u]:
            ps[u] = a
            q.append(u)
            used[u] = True
nx = n - 1
xs = [n-1]
while nx != 0:
    nx = ps[nx]
    xs.append(nx)
l = len(xs) - 2
f = (l + 1)//2
s = l - f

# bfs 0側
used = [-1] * n
used[0] = 0 
q = deque([0])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[-2]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
f += cnt

# bfs n-1側
used = [-1] * n
used[n-1] = 0 
q = deque([n-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[1]:
            q.append(u)
            used[u] = 0
            cnt += 1
# print("cnt",cnt)
s += cnt

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

Submission status: Wrong Answer

Solution code:
n=int(input())
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
fe=[0]*n
sn=[0]*n
from collections import deque
d=deque()
d.append(0)
visited=[False]*n
visited[0]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    fe[i]=fe[g]+1
d=deque()
d.append(n-1)
visited=[False]*n
visited[n-1]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    sn[i]=sn[g]+1
x=0
for i in range(n):
  if fe[i]>sn[i]:
    x+=1
  else:
    x-=1
print(x)
print('Fennec' if x<0 else 'Snuke')

Submission status: Wrong Answer

Solution code:
n=int(input())
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
fe=[0]*n
sn=[0]*n
from collections import deque
d=deque()
d.append(0)
visited=[False]*n
visited[0]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    fe[i]=fe[g]+1
d=deque()
d.append(n-1)
visited=[False]*n
visited[n-1]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    sn[i]=sn[g]+1
x=0
for i in range(n):
  if fe[i]<sn[i]:
    x+=1
  else:
    x-=1
print('Fennec' if x<0 else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N = int(sys.stdin.readline().strip())

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


visited = {"fennec": set(), "snuke": set()}
q = {"fennec": deque([0]), "snuke": deque([N-1])}


while q["fennec"] or q["snuke"]:
    for user in ("fennec", "snuke"):
        if not q[user]:
            continue
        point = q[user].popleft()
        if point in visited["fennec"] or point in visited["snuke"]:
             continue
        visited[user].add(point)
        for point_next in edges[point]:
            q[user].append(point_next)

# print(len(visited["fennec"]), len(visited["snuke"]))
if len(visited["fennec"]) > len(visited["snuke"]):
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N = int(sys.stdin.readline().strip())

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


visited = {"fennec": set(), "snuke": set()}
q = {"fennec": deque([0]), "snuke": deque([N-1])}


while q["fennec"] or q["snuke"]:
    for user in ("fennec", "snuke"):
        if not q[user]:
            continue
        point = q[user].popleft()
        if point in visited["fennec"] or point in visited["snuke"]:
             continue
        visited[user].add(point)
        for point_next in edges[point]:
            q[user].append(point_next)

print(len(visited["fennec"]), len(visited["snuke"]))
if len(visited["fennec"]) > len(visited["snuke"]):
    print("Fennec")
else:
    print("snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
ab = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

sd = [-1]*(N+1)
q = deque()
q.append((1, 0))
while len(q) > 0:
    u, c = q.popleft()
    sd[u] = c
    for v in ab[u]:
        if sd[v] == -1:
            q.append((v, c+1))

ed = [-1]*(N+1)
q = deque()
q.append((N, 0))
while len(q) > 0:
    u, c = q.popleft()
    ed[u] = c
    for v in ab[u]:
        if ed[v] == -1:
            q.append((v, c+1))

sc = 0
for i in range(1, N+1):
    if sd[i] <= ed[i]:
        sc += 1
ec = N-sc
if sc > ec:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
ab = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

sd = [-1]*(N+1)
q = deque()
q.append((1, 0))
while len(q) > 0:
    u, c = q.popleft()
    sd[u] = c
    for v in ab[u]:
        if sd[v] == -1:
            q.append((v, c+1))

ed = [-1]*(N+1)
q = deque()
q.append((N, 0))
while len(q) > 0:
    u, c = q.popleft()
    ed[u] = c
    for v in ab[u]:
        if ed[v] == -1:
            q.append((v, c+1))

sc = 0
for i in range(1, N+1):
    if sd[i] <= ed[i]:
        sc += 1
ec = N-sc
if sc >= ec:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
AB = [list(map(int,input().split())) for _ in range (N-1)]
edge = [[] for _ in range(N)]
for u,v in AB:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

dists = [0]*N
distn = [0]*N
def dfs_s(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        dists[nv] = dists[v] + 1
        dfs_s(nv, v)
    return 
def dfs_n(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        distn[nv] = distn[v] + 1
        dfs_n(nv, v)
    return 
dfs_s(0,-1)
dfs_n(N-1,-1)

B = 0
W = 0
for i in range(N-1):
    if dists[i]<=distn[i]:
        B += 1
    else:
        W += 1

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

Submission status: Wrong Answer

Solution code:
# 2020-05-28 22:45:55

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
ab = [list(map(int,input().split())) for _ in range (N-1)]

edge = [[] for _ in range(N)]
for u,v in ab:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

fromNode = [0] * N
def dfs(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        fromNode[nv] = v
        dfs(nv, v)
    return 

def pathFind(s, g, fromNode):
    path = []
    while s!=g:
        g = fromNode[g]
        if g==s:break
        path.append(g)
    path.reverse()
    return path
dfs(0,-1)
path = pathFind(0,N-1,fromNode)

colors = [-1]*N
for i in range(len(path)):
    if i<=N//2:
        colors[path[i]] = 0
    else:
        colors[path[i]] = 1

def dfs_color(v, p, c):
    for nv in edge[v]:
        if nv==p:continue 
        if colors[nv]==[-1]:
            colors[nv] = c
            dfs_color(nv, v, c)
    return 

dfs_color(0,-1,0)
dfs_color(N-1, -1, 1)
for p in path:
    c = colors[p]
    dfs_color(p, -1, c)

B = 0
W = 0
for c in colors:
    if c==0:B+=1
    elif c==1:W+=1

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