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:
from collections import deque
from copy import deepcopy
N = int( input())
Path = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    Path[a].append(b)
    Path[b].append(a)
Mass = [-1 for _ in range(N)]
F = deque([0])
S = deque([N-1])
while len(F) != 0 or len(S) != 0:
    KF = deque([])
    while len(F) != 0:
        f = F.pop()
        for x in Path[f]:
            if Mass[x] == -1:
                Mass[x] = 1
                KF.append(x)
    F = deepcopy(KF)
    KS = deque([])
    while len(S) != 0:
        s = S.pop()
        for y in Path[s]:
            if Mass[y] == -1:
                Mass[y] = 0
                KS.append(y)
    KF = deepcopy(KS)
if sum(Mass) >= N//2+1:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy
N = int( input())
Path = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    Path[a].append(b)
    Path[b].append(a)
Mass = [-1 for _ in range(N)]
F = deque([0])
S = deque([N-1])
while len(F) != 0 or len(S) != 0:
    KF = deque([])
    while len(F) != 0:
        f = F.pop()
        for x in Path[f]:
            if Mass[x] == -1:
                Mass[x] = 1
                KF.append(x)
    F = deepcopy(KF)
    KS = deque([])
    while len(S) != 0:
        s = S.pop()
        for y in Path[s]:
            if Mass[y] == -1:
                Mass[y] = 0
                KS.append(y)
    KF = deepcopy(KS)
print(Mass)
if sum(Mass) >= N//2+1:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n = int(input())

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

for i in range(n-1):
    f,t = map(int,raw_input().split())
    f -= 1
    t -= 1

    edge[f].append(t)
    edge[t].append(f)

inf = float("inf")
dist1 = [inf for i in range(n)]

dist1[0] = 0
stk = []
for i in edge[0]:
    stk.append([i,1])

while stk:
    t,c = stk.pop()
    if dist1[t] == inf :
        dist1[t] = c
        for i in edge[t]:
            stk.append([i,c+1])

dist2 = [inf for i in range(n)]
dist2[n-1] = 0
for i in edge[n-1]:
    stk.append([i,1])
while stk:
    t,c = stk.pop()
    if dist2[t] == inf :
        dist2[t] = c
        for i in edge[t]:
            stk.append([i,c+1])

fennec = 0
snuke = 0

for i in range(n):
    if dist1[i] <= dist2[i]:
        fennec += 1
    else :
        snuke += 1

print "Fennec" if fennec >= snuke else "Snuke"

Submission status: Wrong Answer

Solution code:
def bfs(branch,n,start):
    arrival = [0 for i in range(n+1)]
    q = [start]
    arrival[q[0]]=1
    while len(q) >= 1:
        for k in range(len(branch[q[0]])):
            if arrival[branch[q[0]][k]] == 0:
                arrival[branch[q[0]][k]] = arrival[q[0]] + 1
                q.append(branch[q[0]][k])
        q.pop(0)
    return arrival

def traceback(graph,start,goal,n):
    arrival = bfs(graph,n,start)
    invarrival = bfs(graph,n,goal)
    path = []
    for i in range(2,n):
        if arrival[i] < arrival[goal] and invarrival[i] < invarrival[start]:
            path.append(i)
    return path
    


n = int(input())
graph = dict()
graphs = dict()
graphg = dict()
for i in range(1,n+1):
    graph[i] = []
    graphs[i] = []
    graphg[i] = []
for i in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
    graphs[a].append(b)
    graphs[b].append(a)

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

path = traceback(graph,1,n,n)
start = 1
goal = n


for i in range(len(path)):
    if path[i] in graphs[start]:
        graphs[start].remove(path[i])
arrivals = bfs(graphs,n,start)
counters = 0
for i in range(len(arrivals)):
    if arrivals[i] > 1:
        counters += 1

for i in range(len(path)):
    if path[i] in graphg[goal]:
        graphg[goal].remove(path[i])

arrivalg = bfs(graphg,n,goal)
counterg = 0
for i in range(len(arrivalg)):
    if arrivalg[i] > 1:
        counterg += 1



if len(path)%2 == 0:
    if counters > counterg:
        print('Fennec')
    else:
        print('Snuke')
else:
    if counters >= counterg:
        print('Fennec')
    else:
        print('Snuke')

Submission status: Wrong Answer

Solution code:
N = int(input())
paths = [[] for i in range(N+1)]
rootinfo = [0 for i in range(N+1)]
judge = [0 for i in range(N+1)]
rootinfo[1] = 2
rootinfo[N] = 3

for i in range(N-1):
    tmp = list(map(int, input().split()))
    if tmp[1] not in paths[tmp[0]]:
        paths[tmp[0]].append(tmp[1])
    if tmp[0] not in paths[tmp[1]]:
        paths[tmp[1]].append(tmp[0])

def searchRoot(start, goal):
    flg = [0 for i in range(N+1)] # 通ったところチェック
    qu = [[start,1,[]]] # 探索用のキュー
    flg[start] = 1
    flg[goal] = 1
    both,root = [],[]
    while True:
        current, depth, root = qu[0][0], qu[0][1], qu[0][2]
        qu.pop(0)
        for ne in paths[current]: # 複数ある場合は両方
            if flg[ne] == 0: # まだめぐっていない場合
                root.append(ne)
                qu.append([ne, depth + 1, root])
                flg[ne] = 1
            else:
                if ne == goal:
                    both = root
                    break
        if len(qu) == 0: # 終了条件
            break
    return both

# 白と黒のスタートどうしで最短経路を探索
b = searchRoot(1, N)
for i in range(len(b)):
    if i <= len(b) // 2:
        rootinfo[b[i]] = 1
    else:
        rootinfo[b[i]] = 2

# 黒
for i in range(2, N):
    if rootinfo[i] == 0:
        b = searchRoot(1, i)
        before = 1
        for i in b:
            if rootinfo[i] == 0:
                rootinfo[i] = before
            before = rootinfo[i]

# 白
for i in range(2, N):
    if rootinfo[i] == 0:
        b = searchRoot(N, i)
        before = 2
        for i in b:
            if rootinfo[i] == 0:
                rootinfo[i] = before
            before = rootinfo[i]


f = rootinfo.count(1)
s = rootinfo.count(2) 
    
if s <= f :
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
import queue
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
q=queue.Queue()
P=[-1 for i in range(N)]
dist=[-1 for i in range(N)]
q.put(0)
#print(G)
dist[0]=0
while(not(q.empty())):
    r=q.get()
    for p in G[r]:
        if dist[p]==-1:
            q.put(p)
            dist[p]=dist[r]+1
            P[p]=r
#print(dist)
S=dist[-1]
#print(P)
L=[];k=N-1
while(k!=-1):
    L.append(k)
    k=P[k]
#fennec:1
#snuke:-1
c=[0 for i in range(N)]
for p in L:
    snuke=dist[p]
    fennec=S-dist[p]
    if fennec>=snuke:
        c[p]=1
    else:
        c[p]=-1
#print(c)
q=queue.Queue()
q.put(0)
reached=[0 for i in range(N)]
reached[0]=1
while(not(q.empty())):
    r=q.get()
    for p in G[r]:
        if reached[p]==0:
            if c[p]!=-1:
                q.put(p)
                c[p]=1
                reached[p]=1
for i in range(N):
    if c[i]==0:
        c[i]=-1
if sum(c)>=0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
N = int(input())
paths = [[] for i in range(N+1)]
for i in range(N-1):
    tmp = list(map(int, input().split()))
    if tmp[1] not in paths[tmp[0]]:
        paths[tmp[0]].append(tmp[1])
    if tmp[0] not in paths[tmp[1]]:
        paths[tmp[1]].append(tmp[0])

def searchRoot(start, goal):
    flg = [0 for i in range(N+1)] # 通ったところチェック
    qu = [[start,1]] # 探索用のキュー
    flg[start] = 1
    flg[goal] = 1
    me, both = 0, 0
    while True:
        current, depth = qu[0][0], qu[0][1]
        qu.pop(0)
        c = 0
        for ne in paths[current]: # 複数ある場合は両方
            if flg[ne] == 0: # まだめぐっていない場合
                qu.append([ne, depth + 1])
                flg[ne] = 1
                c = 1
            else:
                if ne == goal:
                    both += depth - 1 # 塗ってないところで共通のパス
                    c = 1
        if c == 0: #行き止まり
            me += depth - 1
        # print(qu, me, "--", both)
        if len(qu) == 0: # 終了条件
            break
    return me, both

m1, b1 = searchRoot(1, N)
#print(m1)
#print(b1)
m2, b2 = searchRoot(N, 1)
#print(m2)
#print(b2)

s = b1 // 2
f = s
if b1 % 2 == 1:
    f += 1
    
if s + m2 < f + m1:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
N = int(input())
paths = [[] for i in range(N+1)]
for i in range(N-1):
    tmp = list(map(int, input().split()))
    if tmp[1] not in paths[tmp[0]]:
        paths[tmp[0]].append(tmp[1])
    if tmp[0] not in paths[tmp[1]]:
        paths[tmp[1]].append(tmp[0])

def searchRoot(start, goal):
    flg = [0 for i in range(N+1)] # 通ったところチェック
    qu = [[start,1]] # 探索用のキュー
    flg[start] = 1
    flg[goal] = 1
    me, both = 0, 0
    while True:
        current, depth = qu[0][0], qu[0][1]
        qu.pop(0)
        c = 0
        for ne in paths[current]: # 複数ある場合は両方
            if flg[ne] == 0: # まだめぐっていない場合
                qu.append([ne, depth + 1])
                flg[ne] = 1
                c = 1
            else:
                if ne == goal:
                    both += depth - 1 # 塗ってないところで共通のパス
                    c = 1
        if c == 0: #行き止まり
            me += depth - 1
        # print(qu, me, "--", both)
        if len(qu) == 0: # 終了条件
            break
    return me, both

m1, b1 = searchRoot(1, N)
#print(m1)
#print(b1)
m2, b2 = searchRoot(N, 1)
#print(m2)
#print(b2)

s = b1 // 2
f = s
if b1 % 2 == 1:
    f += 1
    
if s + m2 <= f + m1:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

g1 = Graph()
g2 = Graph()

for a, b in ab:
    if a != N and b != N:
        g1.add_edge(a - 1, b - 1)
        g1.add_edge(b - 1, a - 1)
    if a != 1 and b != 1:
        g2.add_edge(a - 1, b - 1)
        g2.add_edge(b - 1, a - 1)

d1 = Dijkstra(g1, 0)
d2 = Dijkstra(g2, N - 1)
c1, c2 = 0, 0
for i in range(N):
    if d1.shortest_distance(i) != float('inf'):
        c1 += 1
    if d2.shortest_distance(i) != float('inf'):
        c2 += 1
if c1 > c2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

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

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

print(f)
print(s)

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

if 0 in p[n - 1]:
    f = [] + p[0]
    f.remove(n - 1)
    score_f = len(f)
    s = [] + p[n - 1]
    s.remove(0)
    score_s = len(s)
    before_f = set([0])
    before_s = set([n - 1])
else:
    f = [0]
    s = [n - 1]
    score_f = 0
    score_s = 0
    before_f = set()
    before_s = set()

collision = 0
while len(f) > 0 or len(s) > 0:
    temp = []
    for x in f:
        temp += p[x]
    temp_f = set(temp) - before_f
    before_f = set(f)
    f = list(temp_f)
    if collision == 0:
        for x in f:
            if x in s:
                s.remove(x)
                f.remove(x)
                collision = 1
                break
    temp = []
    for x in s:
        temp += p[x]
    temp_s = set(temp) - before_s
    before_s = set(s)
    s = list(temp_s)
    if collision == 0:
        for x in s:
            if x in f:
                s.remove(x)
                f.remove(x)
                score_f += 1
                collision = 1
                break
    score_f += len(f)
    score_s += len(s)

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

if 0 in p[n - 1]:
    f = [] + p[0]
    f.remove(n - 1)
    score_f = len(f)
    s = [] + p[n - 1]
    s.remove(0)
    score_s = len(s)
    before_f = set([0])
    before_s = set([n - 1])
else:
    f = [0]
    s = [n - 1]
    score_f = 0
    score_s = 0
    before_f = set()
    before_s = set()
collision = 0
while len(f) > 0 or len(s) > 0:
    temp = []
    for x in f:
        temp += p[x]
    temp_f = set(temp) - before_f
    before_f = set(f)
    f = list(temp_f)
    if collision == 0:
        for x in f:
            if x in s:
                s.remove(x)
                f.remove(x)
                collision = 1
    temp = []
    for x in s:
        temp += p[x]
    temp_s = set(temp) - before_s
    before_s = set(s)
    s = list(temp_s)
    if collision == 0:
        for x in s:
            if x in f:
                s.remove(x)
                f.remove(x)
                score_f += 1
                collision = 1
    score_f += len(f)
    score_s += len(s)

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

if 0 in p[n - 1]:
    f = [] + p[0]
    f.remove(n - 1)
    s = [] + p[n - 1]
    s.remove(0)
else:
    f = [0]
    s = [n - 1]
before_f = set()
before_s = set()
score_f = 0
score_s = 0
collision = 0
while len(f) > 0 or len(s) > 0:
    temp = []
    for x in f:
        temp += p[x]
    temp_f = set(temp) - before_f
    before_f = set(f)
    f = list(temp_f)
    if collision == 0:
        for x in f:
            if x in s:
                s.remove(x)
                f.remove(x)
                collision = 1
    temp = []
    for x in s:
        temp += p[x]
    temp_s = set(temp) - before_s
    before_s = set(s)
    s = list(temp_s)
    if collision == 0:
        for x in s:
            if x in f:
                s.remove(x)
                f.remove(x)
                score_f += 1
                collision = 1
    score_f += len(f)
    score_s += len(s)

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

f = [0]
s = [n - 1]
before_f = set()
before_s = set()
score_f = 0
score_s = 0
collision = 0
while len(f) > 0 or len(s) > 0:
    temp = []
    for x in f:
        temp += p[x]
    temp_f = set(temp) - before_f
    before_f = set(f)
    f = list(temp_f)
    temp = []
    for x in s:
        temp += p[x]
    temp_s = set(temp) - before_s
    before_s = set(s)
    s = list(temp_s)
    if collision == 0:
        for x in s:
            if x in f:
                s.remove(x)
                f.remove(x)
                score_f += 1
                collision = 1
    score_f += len(f)
    score_s += len(s)

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

f = [0]
s = [n - 1]
before_f = set()
before_s = set()
score_f = 0
score_s = 0
collision = 0
while len(f) > 0 or len(s) > 0:
    temp = []
    for x in f:
        temp += p[x]
    temp2 = set(temp)
    temp_f = temp2 - before_f
    before_f = set(f)
    f = list(temp_f)
    temp = []
    for x in s:
        temp += p[x]
    temp2 = set(temp)
    temp_s = temp2 - before_s
    before_s = set(s)
    s = list(temp_s)
    if collision == 0:
        for x in s:
            if x in f:
                s.remove(x)
                f.remove(x)
                score_f += 1
                collision = 1
    score_f += len(f)
    score_s += len(s)

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

f = [0]
s = [n - 1]
before_f = set()
before_s = set()
score_f = 0
score_s = 0
while len(f) > 0 or len(s) > 0:
    temp = []
    for x in f:
        temp += p[x]
    temp2 = set(temp)
    temp_f = temp2 - before_f
    before_f = set(f)
    f = list(temp_f)
    temp = []
    for x in s:
        temp += p[x]
    temp2 = set(temp)
    temp_s = temp2 - before_s
    before_s = set(s)
    s = list(temp_s)
    for x in s:
        if x in f:
            s.remove(x)
            f.remove(x)
            score_f += 1
    score_f += len(f)
    score_s += len(s)

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

f = [0]
s = [n - 1]
before_f = set()
before_s = set()
score_f = 0
score_s = 0
while len(f) > 0 and len(s) > 0:
    temp = []
    for x in f:
        temp += p[x]
    temp2 = set(temp)
    temp_f = temp2 - before_f
    before_f = set(f)
    f = list(temp_f)
    temp = []
    for x in s:
        temp += p[x]
    temp2 = set(temp)
    temp_s = temp2 - before_s
    before_s = set(s)
    s = list(temp_s)
    for x in s:
        if x in f:
            s.remove(x)
            f.remove(x)
            score_f += 1
    score_f += len(f)
    score_s += len(s)

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

Submission status: Wrong Answer

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

sys.setrecursionlimit(10000)


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


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


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


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


def read_str():
    return input()


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


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


def mt(f):
    import time

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

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

    return wrap


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

    f = 1
    s = N

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

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

    # print(fd)
    # print(sd)

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

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

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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

sys.setrecursionlimit(10000)


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


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


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


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


def read_str():
    return input()


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


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


def mt(f):
    import time

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

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

    return wrap


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

    f = 1
    s = N

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

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

    print(fd)
    print(sd)

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

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

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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

sys.setrecursionlimit(10000)


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


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


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


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


def read_str():
    return input()


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


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


def mt(f):
    import time

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

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

    return wrap


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

    f = 1
    s = N

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

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

    fc = 0
    sc = 0
    for i in range(2, N):
        if sd[i] > fd[i]:
            fc += 1
        elif sd[i] < fd[i]:
            sc += 1

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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

queue2 = deque([[n,0]])
visited = [0]*(n+1)
visited[n] = 1
while 0 < len(queue2):
  tmp = queue2.popleft()
  if tmp[0] == 1:
    continue
  for x in p[tmp[0]]:
    if visited[x] == 0:
      queue2.append([x,tmp[1]+1])
      visited[x] = 1
sun = sum(visited) - 2 - path
if path%2 == 0:
  print('Fennec') if sun + 1 <= fen else print('Snuke')
else:
  print('Snuke') if fen + 1 <= sun else print('Fennec')

Submission status: Wrong Answer

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

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

queue2 = deque([[n,0]])
visited = [0]*(n+1)
visited[n] = 1
while 0 < len(queue2):
  tmp = queue2.popleft()
  if tmp[0] == 1:
    continue
  for x in p[tmp[0]]:
    if visited[x] == 0:
      queue2.append([x,tmp[1]+1])
      visited[x] = 1
sun = sum(visited) - 2
if path%2 == 0:
  fen -= (path//2)
  sun -= (path//2)
  print('Fennec') if sun + 1 <= fen else print('Snuke')
else:
  fen -= ((path-1)//2) + 1
  sun -= ((path-1)//2)
  print('Snuke') if fen + 1 <= sun else print('Fennec')

Submission status: Wrong Answer

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

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

queue2 = deque([[n,0]])
visited = [0]*(n+1)
visited[n] = 1
while 0 < len(queue2):
  tmp = queue2.popleft()
  if tmp[0] == 1:
    continue
  for x in p[tmp[0]]:
    if visited[x] == 0:
      queue2.append([x,tmp[1]+1])
      visited[x] = 1
sun = sum(visited) - 2
if fen <= sun:
  print('Snuke')
else:
  print('Fennec')