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
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:
  if fen <= sun:
    print('Snuke')
  else:
    print('Fennec')
else:
  if fen +1 <= sun:
    print('Snuke')
  else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
N = int(input())   
btree = Unionfindtree(N)
wtree = Unionfindtree(N)
table=[]
for i in range(N-1):
    a,b=map(int,input().split())
    table.append([a-1,b-1])
for x,y in table:
    if x==N-1 or y==N-1:
        continue
    btree.union(x,y)
brack=0
for i in range(N):
    if btree.connect(0,i):
        brack+=1
for x,y in table:
    if x==0 or y==0:
        continue
    wtree.union(x,y)
white=0
for i in range(N):
    if btree.connect(N-1,i):
        white+=1

mid = (brack+white)-N
brack-= mid
white-=mid
if mid %2==0:
    brack+= mid//2
    white+=mid//2
else:
    brack+= (mid//2)+1
    white+=mid//2    
    
if brack>white:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)
visit=[[False]*N for i in range(2)]#0が黒、1が白
visit[0][0]=True
visit[0][N-1]=True
visit[1][0]=True
visit[1][N-1]=True
bkei=deque()
bkei.append(0)
brack=1
while bkei:
    i = bkei.popleft()
    for a in table[i]:
        if not visit[0][a]:
            bkei.append(a)
            visit[0][a]=True
            brack+=1
wkei=deque()
wkei.append(N-1)
white=1
while wkei:
    i = wkei.popleft()
    for a in table[i]:
        if not visit[1][a]:
            wkei.append(a)
            visit[1][a]=True
            white+=1

mid = (brack+white)-N
brack-= mid
white-=mid
if mid %2==0:
    brack+= mid//2
    white+=mid//2
else:
    brack+= mid//2+1
    white+=mid//2    
    
if brack>white:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
N = int(input())
g = [[] for _ in range(N+1)]

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

def BFS(v):
        d = [N]*(N+1)
        d[v] = 0
        q = [v]

        while q:
                u = q.pop()
                for i in g[u]:
                        if d[i] == N:
                                d[i] = d[u] + 1
                                q.append(i)

        return d

db = BFS(1)
dw = BFS(N)

b = 0
w = 0

for i in range(1,N+1):
        if db[i] <= dw[i]:
                b += 1
        else:
                w += 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
G = [[] for _ in range(N)]
visited = [0]*N
visited[0],visited[N-1] = 1,1
visited_all = [1]*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)
nextA,nextB = G[0],G[N-1]
scoreA,scoreB = 1,1
while visited != visited_all:
    l = []
    for a in nextA:
        if visited[a] == 0:
            visited[a] = 1
            scoreA += 1
            for x in G[a]:
                l.append(x)
    nextA = l
    for b in nextB:
        if visited[b] == 0:
            visited[b] = 1
            scoreB += 1
            for x in G[b]:
                l.append(x)
    nextB = l
print("Fennec" if scoreA > scoreB else "Snuke")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc067.contest.atcoder.jp/tasks/arc078_b

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


def prepare_graph(edges, N):
    adj = [[] for _ in range(N+1)]
    for a, b in edges:
        adj[a].append([b, 1])
        adj[b].append([a, 1])
    return adj


def dijkstra(adj, s):
    # ダイクストラ法で始点からの距離を計算する
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(adj)
    d = [float('inf')] * len(adj)    # 始点からの距離 計算結果
    d[s] = 0                    #  始点から自身までの距離は0
    pq = []
    heappush(pq, (0, s))
    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue
        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d                    #  計算した距離情報を返す


def solve(edges, N):
    adj = prepare_graph(edges, N)
    f_dist = dijkstra(adj, 1)
    s_dist = dijkstra(adj, N)

    f_point = 0
    s_point = 0
    for f, s in zip(f_dist, s_dist):
        if f > s:
            s_point += 1
        else:
            f_point += 1

    if f_point > s_point:
        return 'Fennec'
    else:
        return 'Snuke'


def main(args):
    edges = []
    N = int(input())
    for _ in range(1, N):
        a, b = map(int, input().split())
        edges.append([a, b])
    ans = solve(edges, N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc067.contest.atcoder.jp/tasks/arc078_b

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


def prepare_graph(edges, N):
    adj = [[] for _ in range(N+1)]
    for a, b in edges:
        adj[a].append([b, 1])
        adj[b].append([a, 1])
    return adj


def dijkstra(adj, s):
    # ダイクストラ法で始点からの距離を計算する
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(adj)
    d = [float('inf')] * len(adj)    # 始点からの距離 計算結果
    d[s] = 0                    #  始点から自身までの距離は0
    pq = []
    heappush(pq, (0, s))
    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue
        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d                    #  計算した距離情報を返す


def solve(edges, N):
    adj = prepare_graph(edges, N)
    f_dist = dijkstra(adj, 1)
    s_dist = dijkstra(adj, N)

    f_point = 0
    s_point = 0
    for f, s in zip(f_dist, s_dist):
        if f > s:
            s_point += 1
        elif f < s:
            f_point += 1
    if f_point > s_point:
        return 'Fennec'
    else:
        return 'Snuke'


def main(args):
    edges = []
    N = int(input())
    for _ in range(1, N):
        a, b = map(int, input().split())
        edges.append([a, b])
    ans = solve(edges, N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
N = int(input())
E = [dict() for _ in range(N+1)]
for i in range(N-1):
	a,b = map(int,input().split(" "))
	E[a][b] = 1
	E[b][a] = 1

fen_count = -1
chil = [0] * (N+1)
def dfs(ver,prev,route):
	global fen_count
	global chil

	fen_count += 1
	flag = -1
	tmp_route = route[:]
	tmp_route.append(ver)
	for nextver in E[ver].keys():
		if nextver == prev:
			pass
		elif nextver == N:
			flag = 1
		else:
			chil[ver] += 1
			lis = dfs(nextver,ver,tmp_route)
			if len(lis) >= 2:
				flag = 1
				tmp_route = lis[:]

	if flag == 1:
		return tmp_route
	else:
		return [0]

route = dfs(1,-1,[])
l = len(route) -1
i = l//2
if i != 0:
	for j in range(i,0,-1):
		fen_count -= (chil[route[-j]])
	fen_count -= 1

if fen_count > (N-2-fen_count):
	print("Fennec")
else:
	print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
N = int(input())
fen_count = 0
E = [dict() for _ in range(N+1)]
for i in range(N-1):
	a,b = map(int,input().split(" "))
	E[a][b] = 1
	E[b][a] = 1

def dfs(ver,prev,rank):
	global fen_count
	flag = -1
	fen_count += 1
	for nextver in E[ver].keys():
		if nextver == prev:
			pass
		elif nextver == N:
			flag = rank
		else:
			flag = max(dfs(nextver,ver,rank+1),flag)

	if flag >= 0:
		return flag
	else:
		return -1

between = dfs(1,-1,0)
ans = fen_count - between 
if between % 2 == 0:
	ans += between // 2
else:
	ans += ((between // 2)+1)


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

Submission status: Wrong Answer

Solution code:
def BFS(i,A,N):
  dist=[0]*N
  d=[-1]*N
  d[i]=0#未訪問ならd=-1,訪問済みならiからの距離
  que=[i]
  dist=1
  while que:
    label=que.pop(0)
    for i in range(len(A[label])):
      if d[A[label][i]]==-1:
        d[A[label][i]]=dist
        que+=[A[label][i]]
    dist+=1
  return(d)

N=int(input())
ab=[]
for i in range(N-1):
  ab.append(list(map(int, input().split())))
A=[ [] for i in range(N) ]
for i in range(N-1):
  A[ab[i][0]-1]+=[ab[i][1]-1]
  A[ab[i][1]-1]+=[ab[i][0]-1]
 

dist1=BFS(0,A,N)
dist2=BFS(N-1,A,N)
Fe=0
Su=0
for i in range(N):
  if dist1[i]<=dist2[i]:
    Fe+=1
  else:
    Su+=1
if Fe>Su:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
def BFS(i,A,N):
  dist=[0]*N
  d=[-1]*N
  d[i]=0#未訪問ならd=-1,訪問済みならiからの距離
  que=[i]
  dist=1
  while que:
    label=que.pop(0)
    for i in range(len(A[label])):
      if d[A[label][i]]==-1:
        d[A[label][i]]=dist
        que+=[A[label][i]]
    dist+=1
  return(d)

N=int(input())
ab=[]
for i in range(N-1):
  ab.append(list(map(int, input().split())))
A=[ [] for i in range(N) ]
for i in range(N-1):
  A[ab[i][0]-1]+=[ab[i][1]-1]
  A[ab[i][1]-1]+=[ab[i][0]-1]

dist1=BFS(0,A,N)
dist2=BFS(N-1,A,N)
Fe=0
Su=0
for i in range(N):
  if dist1[i]<=dist2[i]:
    Fe+=1
  else:
    Su+=1
if Fe>Su:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
def Q4(x):
    N = x[0][0]
    edge = x[1:][:]

    # 隣接リストの作成
    adjacent = [0] * N
    for idx in range(N):
        adjacent[idx] = []
    for idx in range(N - 1):
        tmp = edge[idx][:]
        a = int(tmp[0]) - 1
        b = int(tmp[1]) - 1
        adjacent[a].append(b)
        adjacent[b].append(a)

    # 幅優先探索
    def bfs(N, adjacent, V):
        # 木のある頂点Vからの距離を求める
        dist = [0 for i in range(N)]  # 頂点Vからの距離
        isVisit = [False for i in range(N)]  # ある頂点が探索済か
        queue = [V - 1]  # 幅探索用キュー
        isVisit[V - 1] = True

        while queue:
            u = queue.pop()
            for p in adjacent[u]:
                if not isVisit[p]:
                    isVisit[p] = True
                    dist[p] = dist[u] + 1
                    queue.append(p)
        return dist

    Fennec_dist = bfs(N, adjacent, 1)  # フェネック(頂点1スタート)から各頂点の距離
    Sunuke_dist = bfs(N, adjacent, N)  # すぬけ(頂点Nスタート)
    Fennec_point, Sunuke_point = 0, 0  # 互いに、自分の色を塗れたマスの数

    for idx in range(N):
        if Fennec_dist[idx] <= Sunuke_dist[idx]:
            Fennec_point += 1
        else:
            Sunuke_point += 1
    if Fennec_point > Sunuke_point:
        return 'Fennec'
    else:
        return 'Sunke'

import sys
n = int(input())
l = sys.stdin.readlines()
for idx in range(len(l)):
    l[idx] = l[idx].split()
    l[idx] = list(map(int, l[idx]))
lst = [[n]] + l
print(Q4(lst))

Submission status: Wrong Answer

Solution code:
#!/usr/bin
# -*- coding="utf-8" -*-

a = []
b = [1]
c = 0
d = 0
f = 0
p1 = 0

N = int(input())
for i in range(N-1):
  a.append(list(map(int, input().split())))
  a[i].sort()

def check(num):
  global a
  global b
  global c
  global d
  global f
  global p1
  b = []
  c = c + 1
  for i in range(N-1):
    if a[i][0] in num:
      if a[i][1] < N:
        b.append(a[i][1])
      elif a[i][1] == N:
        d = c
      p1 = p1 + 1
  if len(b) == 0:
    f = 1
  return b

while f == 0:
  check(b)

if d % 2 == 1:
  p1 = p1 + 1

if p1 - d > (N - 1 - d) / 2:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
#!/usr/bin
# -*- coding="utf-8" -*-

a = []
b = [1]
d = 0
f = 0
p1 = 0

N = int(input())
for i in range(N-1):
  a.append(list(map(int, input().split())))
  a[i].sort()

def check(num):
  global a
  global b
  global d
  global f
  global p1
  b = []
  for i in range(N-1):
    if a[i][0] in num:
      if a[i][1] == N:
        d = 0
      if a[i][1] < N:
        b.append(a[i][1])
  if len(b) == 0:
    f = 1
  p1 = p1 + len(b)
  d = d + 1
  return b

while f == 0:
  check(b)

if d % 2 == 1:
  p1 = p1 + 1

if p1 > (N - 1 - d) / 2:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict 
 
N = int(input())
 
g = defaultdict(list)
for i in range(N-1):
    a, b = input().split()
    g[a].append(b)
    g[b].append(a)
 
score = { "f" : 0, "s" : 0 }
front = { "f": ["1"], "s":[str(N)] }
opp = { "f" : "s", "s" : "f" }

for i in range(N):
    if i % 2 == 0:
        t = "f"
    else:
        t = "s"

    node = front[t]
    nn = []
    for n in node:
        for x in g[n]:
            if x not in front["s"] and x not in front["f"]:
                nn.append(x)
                score[t] += 1
    if nn:
        front[t] = nn
    else:
        score[opp[t]] = N - 2 - score[t]
        break
 
if score["f"] > score["s"]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict 

N = int(input())

g = defaultdict(list)
for i in range(N-1):
    a, b = input().split()
    g[a].append(b)
    g[b].append(a)

q = [("f", ["1"]), ("s", [str(N)])]
score = { "f" : 0, "s" : 0 }
f = ["1", "N"]
while q:
    t, node = q.pop(0)
    nn = []
    for n in node:
        for x in g[n]:
            if x not in f:
                nn.append(x)
                f.append(x)
                score[t] += 1
    if nn:
        q.append( (t, nn) )

print(g, score)
if score["f"] > score["s"]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
N = int(input())
tr = [[] for i in range(N)]

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

def canGoCnt(start, wall):
    stack = [start]
    visited = [0 for i in range(N)]
    count = 0
    while stack:
        a = stack.pop()
        visited[a] = 1
        count += 1
        for b in tr[a]:
            if visited[b] == 0 and b != wall:
                stack.append(b)
    return count-1

def route(fr, to):
    stack = [[fr]]
    visited = [0 for i in range(N)]
    while stack:
        rt = stack.pop()
        now = rt[-1]
        if now == to: return rt
        visited[now] = 1
        for nxt in tr[now]:
            if visited[nxt] == 0:
                newrt = rt[:]
                newrt.append(nxt)
                stack.append(newrt)

r = route(0,N-1)
w = (len(r)-1)//2
f = canGoCnt(0, r[w+1])
s = canGoCnt(N-1, r[w])
print ('Fennec' if f >= s else 'Snuke')

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, num):
        self.num = num
        self.connect = []
    def addConnect(self, connected):
        self.connect.append(connected)
    def getConnectNum(self):
        return len(self.connect)
    def getConnect(self):
        return self.connect


if __name__ == '__main__':
    node_num = int(input())
    node = [Node(i+1) for i in range(node_num)]
    ans = []
    vs = ["Fennec","Snuke"]
    for i in range(node_num-1):
        a, b = map(int, input().split())
        node[a-1].addConnect(b)
        node[b-1].addConnect(a)


    for i in range(2):
        node_color = [1] + [0 for j in range(node_num-2)] + [1]
        colored_node = 0
        if i==0:
            queue = [1]
        else:
            queue = [node_num]
        while(len(queue)):
            q = queue.pop()
            node_color[q-1] = 1
            for postnode in node[q-1].getConnect():
                if node_color[postnode-1]==0:
                    queue.append(postnode)
                    colored_node += 1
        ans.append(colored_node)

    if ans[0]!=ans[1]:
        print(vs[ans[0]<ans[1]])
    else:
        print(vs[(ans[0]+1)%2])

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, num):
        self.num = num
        self.connect = []
    def addConnect(self, connected):
        self.connect.append(connected)
    def getConnectNum(self):
        return len(self.connect)
    def getConnect(self):
        return self.connect


if __name__ == '__main__':
    node_num = int(input())
    node = [Node(i+1) for i in range(node_num)]
    ans = []
    vs = ["Fennec","Sunuke"]
    for i in range(node_num-1):
        a, b = map(int, input().split())
        node[a-1].addConnect(b)
        node[b-1].addConnect(a)


    for i in range(2):
        node_color = [1] + [0 for j in range(node_num-2)] + [1]
        colored_node = 0
        if i==0:
            queue = [1]
        else:
            queue = [node_num]
        while(len(queue)):
            q = queue.pop()
            node_color[q-1] = 1
            for postnode in node[q-1].getConnect():
                if node_color[postnode-1]==0:
                    queue.append(postnode)
                    colored_node += 1
        ans.append(colored_node)

    if ans[0]!=ans[1]:
        print(vs[ans[0]<ans[1]])
    else:
        print(vs[(ans[0]+1)%2])

Submission status: Wrong Answer

Solution code:
#coding=UTF-8

N=int(input())
moti=list(range(0,N,1))

#initalize
for idx in range(0,N,1):
    moti[idx]=[]

#input
for idx in range(0,N-1,1):
    mozir=input()
    hyo=mozir.split(' ')
    a=int(hyo[0])-1
    b=int(hyo[1])-1

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

#path 0 to N-1
#width serach
belong=list(range(0,N,1))
for idx in range(0,N,1):
    belong[idx]=None

belong[0]="F"
belong[N-1]="S"

fennec_watch=[0]
sunuke_watch=[N-1]
fennec_haven=1
sunuke_haven=1
fennec_zou=1 #for breaking cond
sunuke_zou=1 #also
Teban="F"
while True:
    if Teban=="F":
        fennec_next=[]
        for mono in fennec_watch:
            kouho=moti[mono]
            for butu in kouho:
                if belong[butu]==None:
                    fennec_next.append(butu)
                    belong[butu]="F"

        fennec_watch=fennec_next
        fennec_zou=len(fennec_next)
        fennec_haven=fennec_haven+fennec_zou
    else:
        sunuke_next=[]
        for mono in sunuke_watch:
            kouho=moti[mono]
            for butu in kouho:
                if belong[butu]==None:
                    sunuke_next.append(butu)
                    belong[butu]="S"

        sunuke_watch=sunuke_next
        sunuke_zou=len(sunuke_next)
        sunuke_haven=sunuke_haven+sunuke_zou
        
    if fennec_zou==0 and sunuke_zou==0:
        break
    Teban='F' if Teban=='S' else 'S'

#when fennec_haven==sunuke_haven==k
#k+1 th turn fennec 33-4
if fennec_haven > sunuke_haven:
    print('Fennec')
else:
    print('Sunuke')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import copy

def now_land(land, op):
    tmp = []
    for i in range(len(land)):
        if land[i] == op:
            tmp.append(i)
    return tmp

def nxt_land(route, now):
    tmp = []
    for i in range(len(route)):
        for j in range(len(now)):
            if route[i][0] == now[j] + 1:
                tmp.append(route[i][1])
            if route[i][1] == now[j] + 1:
                tmp.append(route[i][0])
    return tmp

def chg(land, nxt, op):
    if land[nxt - 1] == -1:
        land[nxt - 1] = op
        return 1, land
    else:
        return 0, land
    

def wide_search(q, route, op):
    tmp = []
    ct = 0
    while len(q) != 0:
        land = q.pop(0)
        now = now_land(land, op)
        nxt = nxt_land(route, now)
        for i in nxt:
            t_land = copy.deepcopy(land)
            rt, t_land = chg(t_land, i, op)
            if rt == 1:
                tmp.append(t_land)
    return len(tmp), tmp

def MAIN(land, route):
    q = [copy.deepcopy(land)]
    while True:
        rt, q = wide_search(q, route, 0)
        if rt == 0:
            print "Snuke"
            break
        rt, q = wide_search(q, route, 1)
        if rt == 0:
            print "Fennic"
            break

if __name__ == '__main__':
    n = input()

    route = []
    route.sort(key = lambda x:x[0])
    land = [-1 for i in range(n)]
    land[0] = 0
    land[len(land) - 1] = 1

    for i in range(n - 1):
        route.append(map(int, raw_input().split()))
    
    MAIN(land, route)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import copy

def now_land(land, op):
    tmp = []
    for i in range(len(land)):
        if land[i] == op:
            tmp.append(i)
    return tmp

def nxt_land(route, now):
    tmp = []
    for i in range(len(route)):
        for j in range(len(now)):
            if route[i][0] == now[j] + 1:
                tmp.append(route[i][1])
    return tmp

def chg(land, nxt, op):
    if land[nxt - 1] == -1:
        land[nxt - 1] = op
        return 1, land
    else:
        return 0, land
    

def wide_search(q, route, op):
    tmp = []
    ct = 0
    while len(q) != 0:
        land = q.pop(0)
        now = now_land(land, op)
        nxt = nxt_land(route, now)
        for i in nxt:
            t_land = copy.deepcopy(land)
            rt, t_land = chg(t_land, i, op)
            if rt == 1:
                tmp.append(t_land)
                ct += 1
    return ct, tmp

def MAIN(land, route):
    q = [copy.deepcopy(land)]
    while True:
        rt, q = wide_search(q, route, 0)
        if rt == 0:
            print "Snuke"
            break
        rt, q = wide_search(q, route, 1)
        if rt == 0:
            print "Fennic"
            break

if __name__ == '__main__':
    n = input()

    route = []
    route.sort(key = lambda x:x[0])
    land = [-1 for i in range(n)]
    land[0] = 0
    land[len(land) - 1] = 1

    for i in range(n - 1):
        route.append(map(int, raw_input().split()))
    
    MAIN(land, route)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import copy

def now_land(land, op):
    tmp = []
    for i in range(len(land)):
        if land[i] == op:
            tmp.append(i)
    return tmp

def nxt_land(route, now):
    tmp = []
    for i in range(len(route)):
        for j in range(len(now)):
            if route[i][0] == now[j] + 1:
                tmp.append(route[i][1])
    return tmp

def chg(land, nxt, op):
    if land[nxt - 1] == -1:
        land[nxt - 1] = op
        return 1, land
    else:
        return 0, land
    

def wide_search(q, route, op):
    tmp = []
    ct = 0
    while len(q) != 0:
        land = q.pop(0)
        now = now_land(land, op)
        nxt = nxt_land(route, now)
        for i in nxt:
            t_land = copy.deepcopy(land)
            rt, t_land = chg(t_land, i, op)
            if rt == 1:
                tmp.append(t_land)
                ct += 1
    return ct, tmp

def MAIN(land, route):
    q = [copy.deepcopy(land)]
    while True:
        rt, q = wide_search(q, route, 0)
        print q
        if rt == 0:
            print "Snuke"
            break
        rt, q = wide_search(q, route, 1)
        if rt == 0:
            print "Fennic"
            break

if __name__ == '__main__':
    n = input()

    route = []
    route.sort(key = lambda x:x[0])
    land = [-1 for i in range(n)]
    land[0] = 0
    land[len(land) - 1] = 1

    for i in range(n - 1):
        route.append(map(int, raw_input().split()))
    
    MAIN(land, route)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())

d = collections.defaultdict(list)
bw = collections.defaultdict(str)

bw[1] = 'b'
bw[n] = 'w'

for _ in range(n - 1):
    u, v = map(int, input().split())
    d[u].append(v)
    d[v].append(u)

q = collections.deque()
q.append(1)
q.append(n)

count = collections.defaultdict(int)

while True:
    if len(q) == 0:
        break

    t = q.popleft()
    count[bw[t]] += 1

    for neighbor in d[t]:
        if bw[neighbor] == '':
            bw[neighbor] = bw[t]
            q.append(neighbor)

if count['b'] <= count['w']:
    print('Sunuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
n=input()
ed=[[] for i in range(n+1)]
for i in range(n-1):
    c,d=map(int,raw_input().split())
    ed[c].append(d)
    ed[d].append(c)
a=[0 for i in range(n+1)]
b=[0 for j in range(n+1)]
visited=[0 for i in range(n+1)]
k=[1]
a[1]=1
visited[1]=1
while k!=[]:
    m=k.pop()
    for i in range(len(ed[m])):
        if visited[ed[m][i]]==0:
            k.append(ed[m][i])
            a[ed[m][i]]=a[m]+1
            visited[ed[m][i]]=1
k=[n]
b[n]=1
visited=[0 for i in range(n+1)]
visited[n]=1
while k!=[]:
    m=k.pop()
    for i in range(len(ed[m])):
        if visited[ed[m][i]]==0:
            k.append(ed[m][i])
            b[ed[m][i]]=b[m]+1
            visited[ed[m][i]]=1
cnt1=0
cnt2=0
for i in range(1,n+1):
    if a[i]>=b[i]: cnt1=cnt1+1
    if a[i]<b[i]: cnt2=cnt2+1
print "Fennec" if cnt1<=cnt2 else"Snuke"

Submission status: Wrong Answer

Solution code:
e = []
N = map(int, raw_input())
for i in range(N[0]-1):
    ai,bi= map(int, raw_input().split())
    if ai > bi:
        tmp = ai
        ai = bi
        bi = tmp
    e.append((ai,bi))
e2 = e[:]
v = []
v.append((1,1))



for i,j in v:
    for s,t in e:
        if s==j :
            v.append((s,t))
            #shortest,append((s,t))
            e.remove((s,t))
            
        # if t == j:
        #     v.append((t,s))
        #     #shortest,append((s,t))
        #     e.remove((s,t))
    if j == N[0]-1:
        break

s = []
num = -1
# i,j = v[-1]
# del v[-1]
k = N[0]
# print(v)
# print(e2)
for i,j in (v[::-1]):
    if j == k:
        num += 1
        k = i
        if (i,j) != (1,1):
            e2.remove((i,j))

# print(num)
kuro = []
kuro.append((1,1))
e3 = e2[:]
# print(e3)
for i,j in kuro:
    # print("(i,j) = ")
    # print((i,j))
    for s,t in e2:
        # print("(s,t) = ")
        # print((s,t))
        if s==j :
            kuro.append((s,t))
            e3.remove((s,t))
kuro.remove((1,1))


lenkuro = len(kuro)
if (num-1) % 2 == 1 and num != 0:
    lenkuro += 1

lenshiro = len(e3)
if lenshiro >= lenkuro:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
e = []
N = map(int, raw_input())
for i in range(N[0]-1):
    ai,bi= map(int, raw_input().split())
    if ai > bi:
        tmp = ai
        ai = bi
        bi = tmp
    e.append((ai,bi))
e2 = e[:]
shortest = []
v = []
v.append((1,1))
for i,j in v:
    for s,t in e:
        if s==j :
            v.append((s,t))
            #shortest,append((s,t))
            e.remove((s,t))
            
        # if t == j:
        #     v.append((t,s))
        #     #shortest,append((s,t))
        #     e.remove((s,t))
    if j == N[0]-1:
        break
del v[0]
s = []
num = 0
# i,j = v[-1]
# del v[-1]
k = N[0]
# print(v)
# print(e2)
for i,j in (v[::-1]):
    if j == k:
        num += 1
        k = i

        e2.remove((i,j))

# print(e2)
# print(num)
kuro = []
kuro.append((1,1))
e3 = e2[:]
# print(e3)
for i,j in kuro:
    # print("(i,j) = ")
    # print((i,j))
    for s,t in e2:
        # print("(s,t) = ")
        # print((s,t))
        if s==j :
            kuro.append((s,t))
            e3.remove((s,t))
kuro.remove((1,1))


lenkuro = len(kuro)
if (num-1) % 2 == 1 and num != 0:
    lenkuro += 1

lenshiro = len(e3)
if lenshiro >= lenkuro:
    print('Snuke')
else:
    print('Fennec')

Submission status: Wrong Answer

Solution code:
e = []
N = map(int, raw_input())
for i in range(N[0]-1):
    ai,bi= map(int, raw_input().split())
    if ai > bi:
        tmp = ai
        ai = bi
        bi = tmp
    e.append((ai,bi))
e2 = e[:]
shortest = []
v = []
v.append((1,1))
for i,j in v:
    for s,t in e:
        if s==j :
            v.append((s,t))
            #shortest,append((s,t))
            e.remove((s,t))
            
        # if t == j:
        #     v.append((t,s))
        #     #shortest,append((s,t))
        #     e.remove((s,t))
    if j == N[0]-1:
        break
del v[0]
s = []
num = 0
# i,j = v[-1]
# del v[-1]
k = N[0]
# print(v)
# print(e2)
for i,j in (v[::-1]):
    if j == k:
        num += 1
        k = i

        e2.remove((i,j))

# print(e2)
# print(num)
kuro = []
kuro.append((1,1))
e3 = e2[:]
# print(e3)
for i,j in kuro:
    # print("(i,j) = ")
    # print((i,j))
    for s,t in e2:
        # print("(s,t) = ")
        # print((s,t))
        if s==j :
            kuro.append((s,t))
            e3.remove((s,t))
kuro.remove((1,1))

lenkuro = len(kuro)
if (num-1) % 2 == 1:
    lenkuro += 1

lenshiro = len(e3)
if lenshiro > lenkuro:
    print('Snuke')
else:
    print('Fennec')