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:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())

#neighbor
#0~N-1でアクセス
ngb = [[] for _ in range(N)]

#入力
#すべて-1ベースに
for _ in range(N-1):
  a,b = mi()
  a -= 1
  b -= 1
  ngb[a].append(b)
  ngb[b].append(a)

start = 0
goal = N-1

#nodes[番号][0]には探索済みならstartからの距離、未探索なら-1を格納
#nodes[番号][1]には（探索済みなら）「何番のノードから来たか(0~N-1)」を格納
nodes = [[-1, -1] for _ in range(N)]

#nodesにスタート地点を入れ、stackを初期化
nodes[start][0] = 0
nodes[start][1] = -1
stack = []
for eachngb in ngb[start]:
  stack.append(eachngb)
  nodes[eachngb][0] = 1
  nodes[eachngb][1] = start

#phase1 start->goalの最短距離を探索
while 1:
  try:
    nownode = stack.pop()
  except:
    break

  if nownode == goal:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if nodes[eachngb][0] == -1:
      stack.append(eachngb)
      #距離を+1して入れ、今のノード番号（どこから来たか、となる）を入れる
      nodes[eachngb][0] = nodes[nownode][0]+1
      nodes[eachngb][1] = nownode

#phase2 B, Wの根を見つける
length = nodes[goal][0] #スタートからゴールへの距離
FenRootPos = length // 2 #Fenの根がある距離
SnRootPos = FenRootPos + 1 #Snukeの根がある距離
FenRoot = -1 #Fenの根ノード番号
SnRoot = -1 #Snukeの根ノード番号

#ゴールからフェネックの根がある場所まで、順に逆走していく
nextnode = goal
#このループ内において、iは今見ているノードのスタートからの距離を表す
for i in range(length, FenRootPos-1, -1):
  nownode = nextnode
  if i == SnRootPos:
    SnRoot = nownode
  elif i == FenRootPos:
    FenRoot = nownode
  nextnode = nodes[nownode][1]

#phase3 B, Wそれぞれの根から、その木のノード数を数える
#お互いの根は探索済み(0)とすることで、重複を避ける

#まずはFen
#探索済みかどうか
ndsFen = [-1] * N
ndsFen[SnRoot] = 0
ndsFen[FenRoot] = 0
stkFen = []
stkFen.append(FenRoot)
FenCnt = 0
while 1:
  try:
    nownode = stkFen.pop()
  except:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if ndsFen[eachngb] == -1:
      stack.append(eachngb)
      #今回は距離は関係無いので、0を入れるだけでいい
      ndsFen[eachngb] = 1
      FenCnt += 1

#次はSnuke
#探索済みかどうか
ndsSn = [-1] * N
ndsSn[FenRoot] = 0
ndsSn[SnRoot] = 0
stkSn = []
stkSn.append(SnRoot)
SnCnt = 0
while 1:
  try:
    nownode = stkSn.pop()
  except:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if ndsSn[eachngb] == -1:
      stack.append(eachngb)
      #今回は距離は関係無いので、0を入れるだけでいい
      ndsSn[eachngb] = 1
      SnCnt += 1

print('Fennec' if FenCnt > SnCnt else 'Snuke')

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())

#neighbor
#0~N-1でアクセス
ngb = [[] for _ in range(N)]

#入力
#すべて-1ベースに
for _ in range(N-1):
  a,b = mi()
  a -= 1
  b -= 1
  ngb[a].append(b)
  ngb[b].append(a)

start = 0
goal = N-1

#nodes[番号][0]には探索済みならstartからの距離、未探索なら-1を格納
#nodes[番号][1]には（探索済みなら）「何番のノードから来たか(0~N-1)」を格納
nodes = [[-1, -1] for _ in range(N)]

#nodesにスタート地点を入れ、stackを初期化
nodes[start][0] = 0
nodes[start][1] = -1
stack = []
for eachngb in ngb[start]:
  stack.append(eachngb)
  nodes[eachngb][0] = 1
  nodes[eachngb][1] = start

#phase1 start->goalの最短距離を探索
while 1:
  try:
    nownode = stack.pop()
  except:
    break

  if nownode == goal:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if nodes[eachngb][0] == -1:
      stack.append(eachngb)
      #距離を+1して入れ、今のノード番号（どこから来たか、となる）を入れる
      nodes[eachngb][0] = nodes[nownode][0]+1
      nodes[eachngb][1] = nownode

#phase2 B, Wの根を見つける
length = nodes[goal][0] #スタートからゴールへの距離
FenRootPos = length // 2 #Fenの根がある距離
SnRootPos = FenRootPos + 1 #Snukeの根がある距離
FenRoot = -1 #Fenの根ノード番号
SnRoot = -1 #Snukeの根ノード番号

#ゴールからフェネックの根がある場所まで、順に逆走していく
nextnode = goal
#このループ内において、iは今見ているノードのスタートからの距離を表す
for i in range(length, FenRootPos-1, -1):
  nownode = nextnode
  if i == SnRootPos:
    SnRoot = nownode
  elif i == FenRootPos:
    FenRoot = nownode
  nextnode = nodes[nownode][1]

#phase3 B, Wそれぞれの根から、その木のノード数を数える
#お互いの根は探索済み(0)とすることで、重複を避ける

#まずはFen
#探索済みかどうか
ndsFen = [-1] * N
ndsFen[SnRoot] = 0
ndsFen[FenRoot] = 0
stkFen = []
stkFen.append(FenRoot)
FenCnt = 0
while 1:
  try:
    nownode = stack.pop()
  except:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if ndsFen[eachngb] == -1:
      stack.append(eachngb)
      #今回は距離は関係無いので、0を入れるだけでいい
      ndsFen[eachngb] = 1
      FenCnt += 1

#次はSnuke
#探索済みかどうか
ndsSn = [-1] * N
ndsSn[FenRoot] = 0
ndsSn[SnRoot] = 0
stkSn = []
stkSn.append(SnRoot)
SnCnt = 0
while 1:
  try:
    nownode = stack.pop()
  except:
    break

  #現在のノードとエッジで繋がるノードのうち、未探索のものをスタックに入れる
  #スタックに入れたらもう探索済みとする
  #木なので、ngb[]が空になっていることはありえない
  for eachngb in ngb[nownode]:
    if ndsSn[eachngb] == -1:
      stack.append(eachngb)
      #今回は距離は関係無いので、0を入れるだけでいい
      ndsSn[eachngb] = 1
      SnCnt += 1

print('Fennec' if FenCnt > SnCnt else 'Snuke')

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())

#neighbor
#0~N-1でアクセス
ngb = [[] for _ in range(N)]
 
#入力
#すべて-1ベースに
for _ in range(N-1):
  a,b = mi()
  a -= 1
  b -= 1
  ngb[a].append(b)
  ngb[b].append(a)

start = 0
goal = N-1

#ノードが[探索済みならstartからの距離、未探索なら-1]を格納
nodes = [-1] * N
#開始地点をいつの時点でスタックに入れるか、またいつの時点でnodesに入れるか？
nodes[start] = 0

st = [start,]
while 1:
  try:
    nownode = st.pop()
  except:
    break

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())
#a1~k~N-1, b1~k~N-1はab[0~k-1~N-2][0], ab[0~k-1~N-2][1]でアクセス
ab = [list(mi()) for _ in range(N-1)]

#neighbor
ngb = [[] for _ in range(N)]

#入力

Submission status: Wrong Answer

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


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):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
#N, M = [int(i) for i in input().split()]
N = int(input())

for i in range(N-1):
    u, v = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, 1)
    g.add_edge(v-1, u-1, 1)

d1 = Dijkstra(g, 0)
d2 = Dijkstra(g, N-1)

ans = 0
for i in range(N):
    if d1.dist[i] <= d2.dist[i]:
        ans += 1

if 2 * ans >= N:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())
#a1~k~N-1, b1~k~N-1はab[0~k-1~N-2][0], ab[0~k-1~N-2][1]でアクセス
ab = [list(mi()) for _ in range(N-1)]

from collections import deque

Submission status: Wrong Answer

Solution code:
N=int(input())
from collections import defaultdict,deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
check={0}
bef=[-2]*N
bef[0]=-1
dist=[float('inf')]*N
dist[0]=0
while len(check)>0:
    now=check.pop()
    for nex in branch[now]:
        if bef[nex]==-2:
            bef[nex]=now
            check|={nex}
            dist[nex]=dist[now]+1
print("NO")
exit()

Submission status: Wrong Answer

Solution code:
N=int(input())
from collections import defaultdict,deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
check={0}
path=[0]*N
path[0]=[0]
while len(check)>0:
    x=check.pop()
    for nex in branch[x]:
        if path[nex]==0:
            check|={nex}
            path[nex]=path[x]+[nex]
print("NO")
exit()
G=path[N-1]
ng=G[(len(G)+1)//2]
cnt=0
for i in range(N):
    if ng not in path[i]:
        cnt+=1
if cnt>N-cnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
N=int(input())
from collections import defaultdict,deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
check={0}
path=[0]*N
path[0]=[0]
while len(check)>0:
    x=check.pop()
    for nex in branch[x]:
        if path[nex]==0:
            check|={nex}
            path[nex]=path[x]+[nex]
G=path[N-1]
ng=G[(len(G)-1)//2]
cnt=0
for i in range(N):
    if ng not in path[i]:
        cnt+=1
if cnt>N-cnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
N=int(input())
from collections import defaultdict,deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
check=deque([[0]])
path=[None]*N
path[0]=[0]
while len(check)>0:
    x=check.popleft()
    for nex in branch[x[-1]]:
        if nex not in x:
            check.append(x+[nex])
            path[nex]=x+[nex]
G=path[N-1]
ng=G[(len(G)-1)//2]
cnt=0
for i in range(N):
    if ng not in path[i]:
        cnt+=1
if cnt>N-cnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*10**5)
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)
# visited = [False for _ in range(N)]
def dfs(start,stop,visitedArray):
    visitedArray[start] = True
    if start == stop:
        return
    else:
        for term in edges[start]:
            if visitedArray[term]:
                continue
            dfs(term,stop,visitedArray)
fennec = [False for _ in range(N)]
snuke = [False for _ in range(N)]
dfs(0,N-1,fennec)
dfs(N-1,0,snuke)
# print(fennec)
# print(snuke)
F = S = C = 0
for i in range(1,N-1):
    if fennec[i] and snuke[i]:
        C += 1
    else:
        if fennec[i]:
            F += 1
        else:
            S += 1
# F = fennec + common//2 + common%2
# S = snuke + common//2
# print(F,S,C)
F += C//2 + C%2
S += C//2
if F > S:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

fenl = [-1 for _ in range(n)]
sunl = [-1 for _ in range(n)]
fenl[0] = 1
sunl[-1] = 1
now = [0]
while now:
  tmp = []
  for _n in now:
    for nxt in nl[_n]:
      if fenl[nxt] == -1:
        tmp.append(nxt)
        fenl[nxt] = fenl[_n] + 1
  now = tmp

now = [n-1]
while now:
  tmp = []
  for _n in now:
    for nxt in nl[_n]:
      if sunl[nxt] == -1:
        tmp.append(nxt)
        sunl[nxt] = sunl[_n] + 1
  now = tmp

fm, sm = 0, 0
for i in range(n):
  if fenl[i] <= sunl[i]:
    fm += 1
  else:
    sm += 1

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

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]
 
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
dp = [0]*n
dp[0] =1
fp = [0]*n
fp[n-1] =1
def bfs(u):
    q = []
    q.append(u)
    while q:
        p = q.pop()
        for i in edges[p]:
            if dp[i] ==0 :
                q.append(i)
                dp[i]+=dp[p]+1
def ffs(u):
    q = []
    q.append(u)
    while q:
        p = q.pop()
        for i in edges[p]:
            if fp[i] ==0 :
                q.append(i)
                fp[i]+=fp[p]+1
bfs(0)
ffs(n-1)
c = 0
for i in range(n):
    if dp[i] <= fp[i]:
        c += 1
if 2*c > n:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = [[] for _ in range(n)]
 
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
dp = [0]*n
dp[0] =1
def bfs(u):
    q = []
    q.append(u)
    while q:
        p = q.pop()
        for i in edges[p]:
            if dp[i] ==0 :
                q.append(i)
                dp[i]+=dp[p]+1
bfs(0)
print("Fennec" if dp[n-1]%2==1 else "Snuke")

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*a=map(int,open(0).read().split())
x=a[1::2]
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix((x,(a[::2],x)),[n+1]*2),0,[1,n])))*2>=n::2])

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*a=map(int,open(0).read().split())
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix((a[::2],(a[::2],a[1::2])),[n+1]*2),0,[1,n])))*2>=n::2])

Submission status: Wrong Answer

Solution code:
from collections import*
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
input=open(0).readline
n=int(input())
f=UnionFind(n)
s=UnionFind(n)
for _ in range(n-1):
    a,b=map(int,input().split())
    if a==1and b==n:continue
    f.unite(a-1,b-1)
    s.unite(a-1,b-1)
a=b=c=0
for i in range(1,n-1):
    x,y=f.same(0,i),s.same(n-1,i)
    if x and y:
        c+=1
    elif x:
        a+=1
    else:
        b+=1
a+=c%2
if b>a:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
N=int(input())

import sys
sys.setrecursionlimit(10**5)
ab=[list(map(int, input().split())) for _ in range (N-1)]
con=[[] for _ in range(N+1)]

#print(ab)
for a,b in ab :
  con[a].append(b)
  con[b].append(a)

#black Fennec
pc=[0]*(N+1)
q=[(1,0)]
vis=[False]*(N+1)
vis[1]=True
Fcnt=N
while q:
  n,c=q.pop()
  pc[n]=c
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
q=[(N,0)]
vis=[False]*(N+1)
vis[1]=True
while q:
  n,c=q.pop()
  if pc[n]>c:
    Fcnt-=1
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
if Fcnt>N-Fcnt:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
N=int(input())
import sys
ab=[list(map(int, input().split())) for _ in range (N-1)]
con=[[] for _ in range(N+1)]

#print(ab)
for a,b in ab :
  con[a].append(b)
  con[b].append(a)

#black Fennec
pc=[0]*(N+1)
q=[(1,0)]
vis=[False]*(N+1)
vis[1]=True
Fcnt=N
while q:
  n,c=q.pop()
  pc[n]=c
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
q=[(N,0)]
vis=[False]*(N+1)
vis[1]=True
while q:
  n,c=q.pop()
  if pc[n]>c:
    Fcnt-=1
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
if Fcnt>=N-Fcnt:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
N=int(input())
import sys
ab=[list(map(int, input().split())) for _ in range (N-1)]
con=[[] for _ in range(N+1)]

#print(ab)
for a,b in ab :
  con[a].append(b)
  con[b].append(a)

#black Fennec
pc=[0]*(N+1)
q=[(1,0)]
vis=[False]*(N+1)
vis[1]=True
Fcnt=N
while q:
  n,c=q.pop()
  pc[n]=c
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
q=[(N,0)]
vis=[False]*(N+1)
vis[1]=True
while q:
  n,c=q.pop()
  if pc[n]>c:
    Fcnt-=1
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
if Fcnt>N-Fcnt:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-

import sys


class UnionFind:
    '''
    配列を用いたUnionFind
    '''

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        '''
        xのグループ番号を返す
        '''
        return self.table[x]

    def union(self, val, y):
        '''
        Fennecは0
         SnukeはN-1とすることで、O(1)にする
         '''
        self.table[y] = val

    def same(self, x, y):
        '''
        xとyが同じグループならtrue
        '''
        x1 = self.find(x)
        y1 = self.find(y)
        return x1 == y1

    def get_table(self):
        return self.table
# python template for atcoder1


sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

Un = UnionFind(N)
S = [N-1]
F = [0]
S_or = N-1
F_or = 0


def oneStep(turn):
    if turn == 1:
        c = S.pop(0)
        for i in adj[c]:
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                Un.union(S_or, i)
                S.append(i)
    else:
        c = F.pop(0)
        for i in adj[c]:
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                Un.union(F_or, i)
                F.append(i)


turn = 0
while S or F:
    if turn == 1:
        if len(S) != 0:
            oneStep(turn)
        turn = 0
    else:
        if len(F) != 0:
            oneStep(turn)
        turn = 1

cntF = Un.get_table().count(0)
cntS = Un.get_table().count(N-1)
if cntF+cntS != N:
    print(2/0)
if cntF > cntS:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-

import sys


class UnionFind:
    '''
    配列を用いたUnionFind
    '''

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        '''
        xのグループ番号を返す
        '''
        return self.table[x]

    def union(self, val, y):
        '''
        Fennecは0
         SnukeはN-1とすることで、O(1)にする
         '''
        self.table[y] = val

    def same(self, x, y):
        '''
        xとyが同じグループならtrue
        '''
        x1 = self.find(x)
        y1 = self.find(y)
        return x1 == y1

    def get_table(self):
        return self.table
# python template for atcoder1


sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

Un = UnionFind(N)
S = [N-1]
F = [0]
S_or = N-1
F_or = 0


def oneStep(turn):
    if turn == 1:
        if len(S) == 0:
            return
        c = S.pop(0)
        for i in adj[c]:
            #print("i->", i)
            #print("i2->", Un.find(i))
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                #print("union Sun", i)
                Un.union(S_or, i)
                S.append(i)
    else:
        if len(F) == 0:
            return
        c = F.pop(0)
        for i in adj[c]:
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                #print("union Fen", i)
                Un.union(F_or, i)
                F.append(i)
    # print(Un.get_table())
    # print(S)
    # print(F)


turn = 0
while S or F:
    # print("step")
    if turn == 1:
        if len(S) != 0:
            oneStep(turn)
        turn = 0
    else:
        if len(F) != 0:
            oneStep(turn)
        turn = 1

# print("end")
# print(Un.get_table())
cnt = Un.get_table().count(0)
if cnt > N-cnt:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-

import sys


class UnionFind:
    '''
    配列を用いたUnionFind
    '''

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        '''
        xのグループ番号を返す
        '''
        return self.table[x]

    def union(self, val, y):
        self.table[y] = val

    def same(self, x, y):
        '''
        xとyが同じグループならtrue
        '''
        x1 = self.find(x)
        y1 = self.find(y)
        return x1 == y1

    def get_table(self):
        return self.table
# python template for atcoder1


sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

Un = UnionFind(N)
S = [N-1]
F = [0]
S_or = N-1
F_or = 0


def oneStep(turn):
    if turn == 1:
        if len(S) == 0:
            return
        c = S.pop(0)
        for i in adj[c]:
            #print("i->", i)
            #print("i2->", Un.find(i))
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                #print("union Sun", i)
                Un.union(S_or, i)
                S.append(i)
    else:
        if len(F) == 0:
            return
        c = F.pop(0)
        for i in adj[c]:
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                #print("union Fen", i)
                Un.union(F_or, i)
                F.append(i)
    # print(Un.get_table())
    # print(S)
    # print(F)


turn = 0
while S or F:
    # print("step")
    if turn == 1:
        if len(S) != 0:
            oneStep(turn)
        turn = 0
    else:
        if len(F) != 0:
            oneStep(turn)
        turn = 1

# print("end")
# print(Un.get_table())
if Un.get_table().count(0) > N/2:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-

import sys


class UnionFind:
    '''
    配列を用いたUnionFind
    '''

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        '''
        xのグループ番号を返す
        '''
        return self.table[x]

    def union(self, x, y):
        '''
        xとyが同じグループならFalse
        xとyが違うグループなら、同じグループにする(くっつける)
        '''
        x1 = self.find(x)
        y1 = self.find(y)

        if x1 == y1:
            return False

        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True

    def same(self, x, y):
        '''
        xとyが同じグループならtrue
        '''
        x1 = self.find(x)
        y1 = self.find(y)
        return x1 == y1

    def get_table(self):
        return self.table
# python template for atcoder1


sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

Un = UnionFind(N)
S = [N-1]
F = [0]
S_or = N-1
F_or = 0


def oneStep(turn):
    if turn == 1:
        if len(S) == 0:
            return
        c = S.pop(0)
        for i in adj[c]:
            #print("i->", i)
            #print("i2->", Un.find(i))
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                #print("union Sun", i)
                Un.union(S_or, i)
                S.append(i)
    else:
        if len(F) == 0:
            return
        c = F.pop(0)
        for i in adj[c]:
            if not Un.same(S_or, i) and not Un.same(F_or, i):
                #print("union Fen", i)
                Un.union(F_or, i)
                F.append(i)
    # print(Un.get_table())
    # print(S)
    # print(F)


turn = 0
while S or F:
    # print("step")
    if turn == 1:
        if len(S) != 0:
            oneStep(turn)
        turn = 0
    else:
        if len(F) != 0:
            oneStep(turn)
        turn = 1

# print("end")
# print(Un.get_table())
if Un.get_table().count(0) > Un.get_table().count(N-1):
    ans = "Fennec"
else:
    ans = "Sunuke"
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b = inpl()
    path[a].append(b)
    path[b].append(a)

inf = float('inf')
ctr = 1
now = {1}
distF = [inf for _ in range(N+1)]
distF[1] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
ctr = 1
now = {N}
distS = [inf for _ in range(N+1)]
distS[N] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distS[nb] > distS[na] + 1:  
                distS[nb] = distS[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
D = distF[N]
for i in range(1,N+1):
    if distF[i] == D//2 and distF[i]+distS[i] == D:
        St = i
    if distF[i] == D//2 + 1 and distF[i]+distS[i] == D:
        En = i
path[St].remove(En)
path[En].remove(St)

ctr = 1
now = {1}
distF = [inf for _ in range(N+1)]
distF[1] = 0
ctr1 = 0
while ctr1 != ctr:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
    ctr1 = ctr
if 2*ctr > N:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

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

inf = 10**6


fvisited = [inf for _ in range(n+1)]
fvisited[n] = 0
q = deque([n])
while len(q)>0:
    s = q.popleft()
    for e in edge[s]:
        if fvisited[e]==inf:
            fvisited[e] = fvisited[s]+1
            q.append(e)

svisited = [inf for _ in range(n+1)]
svisited[1] = 0
q = deque([1])
while len(q)>0:
    s = q.popleft()
    for e in edge[s]:
        if svisited[e]==inf:
            svisited[e] = svisited[s]+1
            q.append(e)

# print(fvisited)
# print(svisited)
fcnt = 0
scnt = 0
for i in range(1,n+1):
    if fvisited[i]<=svisited[i]:
        fcnt += 1
    else:
        scnt += 1

if fcnt<scnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
edge = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

inf = 10**5

fvisited = [inf for _ in range(n+1)]
fvisited[n] = 0
while True:
    flag = False
    for i in range(1,n+1):
        for e in edge[i]:
            if fvisited[e]!=min(fvisited[e],fvisited[i]+1):
                flag = True
            fvisited[e] = min(fvisited[e],fvisited[i]+1)
    if not flag:
        break

svisited = [inf for _ in range(n+1)]
svisited[1] = 0
while True:
    flag = False
    for i in range(1,n+1):
        for e in edge[i]:
            if svisited[e]!=min(svisited[e],svisited[i]+1):
                flag = True
            svisited[e] = min(svisited[e],svisited[i]+1)
    if not flag:
        break

fcnt = 0
scnt = 0
for i in range(1,n+1):
    if svisited[i] < fvisited[i]:
        scnt += 1
    else:
        fcnt += 1

if scnt<fcnt:
    print("Snuke")
else:
    print("Fennec")

Submission status: Wrong Answer

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

def dfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
    return d

ans=0
for i,j in zip(dfs(0),dfs(n-1)):
    if i<=j:ans+=1
if ans<n/2:print('Snuke')
else:print('Fennec')