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
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:
                        heapq.heappush(queue,(w,j,k))

        return gb


class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False):
        self.v = v
        self.directed = directed
        self.edge = []

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
            

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():
    n = int(input())
    
    edge = [tuple([int(t)-1 for t in input().split()])for _ in [0]*(n-1)]

    gb = GraphBuilder(n)
    gb.addEdges(edge,False)

    g = gb.buildGraph()

    node = [0]*n

    head = [0]
    tail = [n-1]
    
    while len(head)>0 or len(tail)>0:
        t = []
        while len(head)>0:
            h = head.pop()
            for i in g.neighbor[h]:
                if node[i]==0:
                    t.append(i)
                    node[i] = 1
        head = t

        t = []
        while len(tail)>0:
            h = tail.pop()
            for i in g.neighbor[h]:
                if node[i]==0:
                    t.append(i)
                    node[i] = -1
        tail = t

    ans = sum(node)
    if ans>0:
        print("Fennec")
    else:
        print("Snuke")

Submission status: Wrong Answer

Solution code:
import heapq
 
"""
https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC%28heapq%29%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
"""
 
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
 
################################
N = int(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b = map(int,input().split())
    edge[a-1].append([1,b-1])
    edge[b-1].append([1,a-1])

dist_zero = dijkstra_heap(0,edge)
dist_n = dijkstra_heap(N-1,edge)
"""
print(dist_zero)
print(dist_n)
"""
b = 0
w = 0

for black,white in zip(dist_zero,dist_n):
    if black == white:
        continue
    elif black > white:
        w += 1
    else:
        b += 1

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

Submission status: Wrong Answer

Solution code:
import heapq
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:
                        heapq.heappush(queue,(w,j,k))

        return gb


class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False):
        self.v = v
        self.directed = directed
        self.edge = []

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
            

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():
    n = int(input())
    
    edge = [tuple([int(t)-1 for t in input().split()])for _ in [0]*(n-1)]

    gb = GraphBuilder(n)
    gb.addEdges(edge,False)

    g = gb.buildGraph()

    node = [0]*n

    head = [0]
    tail = [n-1]
    
    while len(head)>0 and len(tail)>0:
        t = []
        while len(head)>0:
            h = head.pop()
            for i in g.neighbor[h]:
                if node[i]==0:
                    t.append(i)
                    node[i] = 1
        head = t

        t = []
        while len(tail)>0:
            h = tail.pop()
            for i in g.neighbor[h]:
                if node[i]==0:
                    t.append(i)
                    node[i] = -1
        tail = t

    ans = sum(node)
    if ans>0:
        print("Fennec")
    else:
        print("Snuke")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
 
"""
https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC%28heapq%29%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
"""
 
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
 
################################
N = int(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b = map(int,input().split())
    edge[a-1].append([1,b-1])
    edge[b-1].append([1,a-1])

dist_zero = dijkstra_heap(0,edge)
dist_n = dijkstra_heap(N-1,edge)
"""
print(dist_zero)
print(dist_n)
"""
b = 0
w = 0
for black,white in zip(dist_zero,dist_n):
    if black == white:
        continue
    elif black >= white:
        w += 1
    else:
        b += 1

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

Submission status: Wrong Answer

Solution code:
import heapq
 
"""
https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC%28heapq%29%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
"""
 
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
 
################################
N = int(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b = map(int,input().split())
    edge[a-1].append([1,b-1])
    edge[b-1].append([1,a-1])

dist_zero = dijkstra_heap(0,edge)
dist_n = dijkstra_heap(N-1,edge)
"""
print(dist_zero)
print(dist_n)
"""
b = 0
w = 0
for black,white in zip(dist_zero,dist_n):
    if black >= white:
        w += 1
    else:
        b += 1

if b >= w:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import heapq
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:
                        heapq.heappush(queue,(w,j,k))

        return gb


class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False):
        self.v = v
        self.directed = directed
        self.edge = []

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
            

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():
    n = int(input())
    
    edge = [tuple([int(t)-1 for t in input().split()])for _ in [0]*(n-1)]

    gb = GraphBuilder(n)
    gb.addEdges(edge,False)

    g = gb.buildGraph()

    node = [0]*n

    head = [0]
    tail = [n-1]
    
    while len(head)>0 and len(tail)>0:
        t = []
        while len(head)>0:
            h = head.pop()
            for i in g.neighbor[h]:
                if node[i]==0:
                    t.append(i)
                    node[i] = 1
        head = t

        t = []
        while len(tail)>0:
            h = tail.pop()
            for i in g.neighbor[h]:
                if node[i]==0:
                    t.append(i)
                    node[i] = -1
        tail = t

    ans = sum(node)
    if ans>=0:
        print("Fennec")
    else:
        print("Snuke")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    C = [0] * N
    B = set([0])
    W = set([N - 1])
    C[0] = 1
    C[-1] = -1
    while B or W:
        BN = set()
        for b in B:
            for bb in E[b]:
                if bb != b and C[bb] == 0:
                    C[bb] = 1
                    BN.add(bb)
        B = BN
        WN = set()
        for w in W:
            for ww in E[w]:
                if ww != w and C[ww] == 0:
                    C[ww] = -1
                    WN.add(ww)
        W = WN
    return 'Fennec' if C.count(1) > C.count(-1) else 'Sunuke'

print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    C = [0] * N
    B = set([0])
    W = set([N - 1])
    while B or W:
        BN = set()
        for b in B:
            for bb in E[b]:
                if bb != b and C[bb] == 0:
                    C[bb] = 1
                    BN.add(bb)
        B = BN
        WN = set()
        for w in W:
            for ww in E[w]:
                if ww != w and C[ww] == 0:
                    C[ww] = -1
                    WN.add(ww)
        W = WN
    return 'Fennec' if C.count(1) > C.count(-1) else 'Sunuke'

print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    B = set([0])
    W = set([N - 1])
    bc, wc = 1, 1
    while B and W:
        BN = set()
        for b in B:
            for bb in E[b]:
                if bb == b:
                    continue
                if bb in W:
                    collided = True
                    continue
                BN.add(bb)
        B = BN
        bc += len(B)
        WN = set()
        for w in W:
            for ww in E[w]:
                if ww == w:
                    continue
                if ww in B:
                    collided = True
                    continue
                WN.add(ww)
        W = WN
        wc += len(WN)
    if not B:
        wc = N - bc
    else:
        bc = N - wc
    return 'Fennec' if bc > wc else 'Sunuke'

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from collections import deque
N=int(input())

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

dist_f=[-1]*(N+1)
d=0
queue=[1]
while queue:  
  new_queue=set()
  for u in queue:
    dist_f[u]=d
    for v in graph[u]:
      if dist_f[v]==-1:
        new_queue.add(v)
        
  queue=list(new_queue)
  d+=1
print(dist_f)

dist_s=[-1]*(N+1)
d=0
queue=[N]
while queue:  
  new_queue=set()
  for u in queue:
    dist_s[u]=d
    for v in graph[u]:
      if dist_s[v]==-1:
        new_queue.add(v)
        
  queue=list(new_queue)
  d+=1
print(dist_s)

cnt_f,cnt_s=0,0
for i in range(1,N+1):
  if dist_f[i]<=dist_s[i]:
    cnt_f+=1
  else:
    cnt_s+=1
print(cnt_f,cnt_s)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

edges = [[] for _ in range(N + 1)]
for u, v in X:
    edges[u].append(v)
    edges[v].append(u)

d = [-1] * (N + 1)
d[1] = 0
q = deque([1])
while q:
    u = q.popleft()
    for v in edges[u]:
        if d[v] >= 0:
            continue
            
        d[v] = d[u] + 1
        q.append(v)
        
if d[-1] % 2 != 0 or d[-1] == 1:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

edges = [[] for _ in range(N + 1)]
for u, v in X:
    edges[u].append(v)
    edges[v].append(u)

d = [-1] * (N + 1)
d[1] = 0
q = deque([1])
while q:
    u = q.popleft()
    for v in edges[u]:
        if d[v] >= 0:
            continue
            
        d[v] = d[u] + 1
        q.append(v)
        
if d[-1] % 2 == 0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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


from collections import deque
seen = [False for _ in range(n)]
child = [[] for _ in range(n)]
par = [0 for _ in range(n)]
order = []
que = deque()
que.append(0)
seen[0] = True

while que:
    v = que.popleft()
    order.append(v)
    for to in edges[v]:
        if not seen[to]:
            seen[to] = True
            par[to] = v
            que.append(to)
            child[v].append(to)

d = [-1 for _ in range(n)]
c = [0 for _ in range(n)]
for i in order:
    d[i] = d[par[i]] + 1
for i in order[::-1]:
    if len(child[i]) == 0:
        continue
    for ch in child[i]:
        c[i] += c[ch] + 1



point = n - 1
move_s = (d[n-1] - 1) // 2
move_f = d[n-1] - 1 - move_s
for i in range((d[n-1] - 1) // 2):
    point = par[point]

cnt_s = c[point] + 1 - (move_s + 1)
cnt_f = n - (c[point] + 1) - (move_f + 1)

print('Fennec' if cnt_f > cnt_s else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n = int(input()) #n:頂点数　w:辺の数
w = n - 1

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    z = 1
    edge[x].append([z,y])
    edge[y].append([z,x]) 

dis_from_f = dijkstra_heap(0)
dis_from_s = dijkstra_heap(n - 1)

cnt = 0
for i, j in zip(dis_from_f, dis_from_s):
    if i <= j:
        cnt += 1
if cnt > n - cnt:
    print("Fennec")
else:
    print("Snuke")
print(dis_from_f)
print(dis_from_s)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n = int(input()) #n:頂点数　w:辺の数
w = n - 1

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    z = 1
    edge[x].append([z,y])
    edge[y].append([z,x]) 

dis_from_f = dijkstra_heap(0)
dis_from_s = dijkstra_heap(n - 1)

cnt = 0
for i, j in zip(dis_from_f, dis_from_s):
    if i <= j:
        cnt += 1
if cnt >= n - cnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

n = int(input())

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

dist_1 = [0 for _ in range(n)]
dist_n = [0 for _ in range(n)]

q = deque()
q.append((0, -1, 0))
while len(q) > 0:
    num, f_num, dist = q.popleft()
    for node in edges[num]:
        if node == f_num:
            continue
        else:
            dist_1[node] = dist + 1
            q.append((node, num, dist+1))
q = deque()
q.append((n-1, -1, 0))
while len(q) > 0:
    num, f_num, dist = q.popleft()
    for node in edges[num]:
        if node == f_num:
            continue
        else:
            dist_n[node] = dist + 1
            q.append((node, num, dist+1))

ans = 0
for i in range(n):
    if dist_1[i] < dist_n[i]:
        ans += 1

fennec = ans
snuke = n - fennec
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
g = [[]*n for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

visited = [False]*n
que = deque([(0)])
x = 0
while que:
    idx= que.popleft()
    if idx==n-1:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    x += 1
    for to in g[idx]:
        que.append((to))

visited = [False]*n
que = deque([(n-1)])
y = 0
while que:
    idx= que.popleft()
    if idx==0:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    y += 1
    for to in g[idx]:
        que.append((to))

que = deque([(0,0)])
visited = [False]*n
while que:
    idx, c = que.popleft()
    if visited[idx]:
        continue
    visited[idx] = c
    for to in g[idx]:
        que.append((to, c+1))
mid = visited[n-1]-1

tx = x-mid-1
ty = y-mid-1
if mid%2!=0:
    tx += 1
print('Fennec' if tx>ty else 'Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
g = [[]*n for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

visited = [False]*n
que = deque([(0)])
x = 0
while que:
    idx= que.popleft()
    if idx==n-1:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    x += 1
    for to in g[idx]:
        que.append((to))

visited = [False]*n
que = deque([(n-1)])
y = 0
while que:
    idx= que.popleft()
    if idx==0:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    y += 1
    for to in g[idx]:
        que.append((to))

que = deque([(0,0)])
visited = [False]*n
while que:
    idx, c = que.popleft()
    if visited[idx]:
        continue
    visited[idx] = c
    for to in g[idx]:
        que.append((to, c+1))
mid = visited[n-1]-1

if mid%2==0:
    print('Fennec' if x>y else 'Snuke')
else:
    print('Fennec' if x>=y else 'Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
g = [[]*n for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

visited = [False]*n
que = deque([(0)])
x = 0
while que:
    idx= que.popleft()
    if idx==n-1:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    x += 1
    for to in g[idx]:
        que.append((to))

visited = [False]*n
que = deque([(n-1)])
y = 0
while que:
    idx= que.popleft()
    if idx==0:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    y += 1
    for to in g[idx]:
        que.append((to))

que = deque([(0,0)])
visited = [False]*n
while que:
    idx, c = que.popleft()
    if visited[idx]:
        continue
    visited[idx] = c
    for to in g[idx]:
        que.append((to, c+1))
mid = visited[n-1]-1

if mid%2!=0:
    x += 1
print('Fennec' if x>y else 'Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
g = [[]*n for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

visited = [False]*n
que = deque([(0)])
x = 0
while que:
    idx= que.popleft()
    if idx==n-1:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    x += 1
    for to in g[idx]:
        que.append((to))

visited = [False]*n
que = deque([(n-1)])
y = 0
while que:
    idx= que.popleft()
    if idx==0:
        continue
    if visited[idx]:
        continue
    visited[idx]=True
    y += 1
    for to in g[idx]:
        que.append((to))
print('Fennec' if x>y else 'Snuke')