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:
N = input()
mas = list(map(str, range(2, int(N))))
l = []
for i in range(int(N)-1):
    l.append(list(map(int, input().split())))
fen, fenpoint = ['1'], 0
snu, snupoint = [N], 0

num = 0
while True:
    if num % 2 == 0:
        for i in fen:
            if not i == '1':
                mas.remove(i)
                fen.remove(i)
            fenpoint+=1
            for e in l:
                if i in e:
                    e.remove(i)
                    if not e == []:
                        fen.append(e[0])
                        mas.remove(e[0])
        last_fenpoint = fenpoint
    else:
        for i in snu:
            if not i == N:
                mas.remove(i)
                snu.remove(i)
            snupoint+=1
            for e in l:
                if i in e:
                    e.remove(i)
                    if not e == []:
                        snu.append(e[0])
                        mas.remove(e[0])
        last_snupoint = snupoint
    num+=1
    try:
        if last_snupoint == snupoint and last_fenpoint == fenpoint:
            break
    except:
        pass

if fenpoint >= int(N)/2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
N = input()
mas = list(map(str, range(2, int(N))))
l = []
for i in range(int(N)-1):
    l.append(list(map(int, input().split())))
fen, fenpoint = ['1'], 0
snu, snupoint = [N], 0
 
num = 0
while True:
    if num % 2 == 0:
        for i in fen:
            if not i == '1':
                mas.remove(i)
                fen.remove(i)
            fenpoint+=1
            for e in l:
                if i in e:
                    e.remove(i)
                    if not e == []:
                        fen.append(e[0])
                        mas.remove(e[0])
        last_fenpoint = fenpoint
    else:
        for i in snu:
            if not i == N:
                mas.remove(i)
                snu.remove(i)
            snupoint+=1
            for e in l:
                if i in e:
                    e.remove(i)
                    if not e == []:
                        snu.append(e[0])
                        mas.remove(e[0])
        last_snupoint = snupoint
    num+=1
    try:
        if last_snupoint == snupoint and last_fenpoint == fenpoint:
            break
    except:
        pass
 
if fenpoint > snupoint:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
N = input()
mas = list(map(str, range(2, int(N))))
l = []
for i in range(int(N)-1):
    l.append(list(map(int, input().split())))
fen, fenpoint = ['1'], 0
snu, snupoint = [N], 0

num = 0
while True:
    if num % 2 == 0:
        for i in fen:
            if not i == '1':
                mas.remove(i)
                fen.remove(i)
            fenpoint+=1
            for e in l:
                if i in e:
                    e.remove(i)
                    if not e == []:
                        fen.append(e[0])
                        mas.remove(e[0])
        last_fenpoint = fenpoint
    else:
        for i in snu:
            if not i == N:
                mas.remove(i)
                snu.remove(i)
            snupoint+=1
            for e in l:
                if i in e:
                    e.remove(i)
                    if not e == []:
                        snu.append(e[0])
                        mas.remove(e[0])
        last_snupoint = snupoint
    num+=1
    try:
        if last_snupoint == snupoint and last_fenpoint == fenpoint:
            break
    except:
        pass

if fenpoint > snupoint:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:
N = input()
mas = list(map(str, range(2, int(N))))
l = []
for i in range(int(N)-1):
    l.append(list(map(int, input().split())))
fen, fenpoint = ['1'], 0
snu, snupoint = [N], 0

num = 0
while True:
    if num % 2 == 0:
        for i in fen:
            if not i == '1':
                mas.remove(i)
                fen.remove(i)
            fenpoint+=1
            for e in l:
                if i in e:
                    e.remove(i)
                    if not e == []:
                        fen.append(e[0])
                        mas.remove(e[0])
        last_fenpoint = fenpoint
    else:
        for i in snu:
            if not i == N:
                mas.remove(i)
                snu.remove(i)
            snupoint+=1
            for e in l:
                if i in e:
                    e.remove(i)
                    if not e == []:
                        snu.append(e[0])
                        mas.remove(e[0])
        last_snupoint = snupoint
    num+=1
    try:
        if last_snupoint == snupoint and last_fenpoint == fenpoint:
            break
    except:
        pass

if fenpoint >= snupoint:
    print('Fennec')
else:
    print('Snuke')

Submission status: Wrong Answer

Solution code:

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}


        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):

        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()
        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    #print("updated")
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break


        return dists

    def search(self):
        global N
        a=1
        b=N-1
        visit=[0]*(N+1)

        Qa=[a]
        Qb=[b]
        visit[a]=visit[b]=1

        while True:
            

            try:
                a=Qa.pop()
            except:
                res="Snuke"
                break


            sss=list(self.adj[a])
            if len(sss)==0:
                res="Snuke"
                break

            #print(sss)
            for sa in sss:
                if not visit[sa]:
                    Qa.append(sa)
                    visit[sa]=1

            try:
                b=Qb.pop()
            except:
                res="Fennec"
                break

            sss=list(self.adj[b])
            if len(sss)==0:
                res="Fennec"
                break

            for sb in sss:
                if not visit[sb]:
                    Qb.append(sb)
                    visit[sb]=1

Submission status: Wrong Answer

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))

N = ri()
rel = [[] for _ in range(N+1)]
s = []
color = [-1 for _ in range(N+1)]
j = [-1 for _ in range(N+1)]
nim = []
fe = []
sn = []

def dfs_visit(u):
    s.append(u)
    color[u] = 0
    j[u] = -1
    s_tmp = []
    while(s != list()):
        j[u] += 1
        u = s[-1]
        try:
            v = rel[u][j[u]]
        except IndexError:
            if(s[0] == 1 and s[-1] == N):
                nim.append(len(s)-2)
            elif(not set(s).issubset(set(s_tmp))):
                if(1 in s and not (1 in s and N in s)):
                    fe.append(len(s)-1)
                else:
                    sn.append(len(s))
                s_tmp = s[:]
            s.pop()
            color[u] = 1
            continue
        if(color[v] == -1):
            color[v] = 0
            s.append(v)

def dfs():
    for i in range(N):
        if(color[i] == -1):
            dfs_visit(i)

for i in range(N-1):
    a,b = rli()
    rel[a].append(b)
    rel[b].append(a)

dfs()
fe = sum(fe)
nim = nim[0]
sn = N - fe - nim
ans = 0

if(nim % 2 == 1): sn -= 1
if(fe <= sn):
    ans = 1
print("Fennec" if ans == 0 else "Snuke")

Submission status: Wrong Answer

Solution code:

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}


        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):

        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()
        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    #print("updated")
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break


        return dists

    def search(self):
        global N
        a=1
        b=N-1
        visit=[0]*(N+1)

        Qa=[a]
        Qb=[b]
        visit[a]=visit[b]=1

        while True:
            

            try:
                a=Qa.pop()
            except:
                res="Snuke"
                break


            sss=list(self.adj[a])
            if len(sss)==0:
                res="Snuke"
                break

            #print(sss)
            for sa in sss:
                if not visit[sa]:
                    Qa.append(sa)
                    visit[sa]=1

            try:
                b=Qb.pop()
            except:
                res="Fennec"
                break

            sss=list(self.adj[b])
            if len(sss)==0:
                res="Fennec"
                break

            for sb in sss:
                if not visit[sb]:
                    Qb.append(sb)
                    visit[sb]=1



            if sum(visit)==N-1:
                break


        print(res)

Submission status: Wrong Answer

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

queue = collections.deque([1])
mf = [False] * (n+1)
mf[1] = True
count1 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != n:
            mf[node] = True
            count1 += 1
            queue.append(node)
queue = collections.deque([n])
mf = [False] * (n+1)
mf[n] = True
count2 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != 1:
            mf[node] = True
            count2 += 1
            queue.append(node)

if (count1+count2-(n-2)) % 2 == 1 :
    if count2 > count1:
        print("Snuke")
    else:
        print("Fennec")
else:
   if count1 > count2:
        print("Fennec")
   else:
        print("Snuke")

Submission status: Wrong Answer

Solution code:

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

def solve(N, Es):
    if N == 2:
        return "Snuke"
    path = find_path(N, 0, N - 1, Es)
    len_path = len(path)
    a = (len_path - 1)// 2
    b = a + 1
    p1 = path[a]
    p2 = path[b]
    e1 = count_edges(N, p1, p2, Es)
    e2 = N - e1
    if e1 > e2:
        return "Fennec"
    else:
        return "Snuke"

def find_path(N, s, g, Es):
    stack = [(s, 0)]
    path = [(s, 0)]
    visited = [False] * N
    visited[s] = True
    while True:
        v, d = stack.pop()
        if (path and path[-1][1] == d):
            path.pop()
        path.append((v, d))
        for u in Es[v]:
            if visited[u]:
                continue
            stack.append((u, d + 1))
            visited[u] = True;
            if u == g:
                path = [p for p, depth in path] + [g]
                return path

def count_edges(N, p1, p2, Es):
    stack = [p1]
    visited = [False] * N
    visited[p1] = True
    visited[p2] = True
    count = 0
    while stack:
        v = stack.pop()
        count += 1
        for u in Es[v]:
            if visited[u]:
                continue
            stack.append(u)
            visited[u] = True
    return count


N, Es = read_data()
print(solve(N, Es))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    edges = collections.defaultdict(list)
    for __ in range(N - 1):
        a, b = ILI()
        edges[a].append(b)
        edges[b].append(a)
    return N, edges


def solve(N, edges):
    queue_from_f = set()
    queue_from_s = set()
    queue_from_f.add(1)
    queue_from_s.add(N)

    n_node_f = 1
    snuke_bool = True

    visited_f = [False] * (N + 1)
    visited_s = [False] * (N + 1)
    visited_f[0], visited_f[1] = True, True
    visited_s[0], visited_s[N] = True, True

    while len(queue_from_f) != 0:
        f_next_queue = set()
        for i in queue_from_f:
            next_point = edges[i]
            for point in next_point:
                if snuke_bool and point in queue_from_s:
                    snuke_bool = False
                    visited_f[point] = True

                if visited_f[point]:
                    continue
                else:
                    f_next_queue.add(point)
                    visited_f[point] = True

        n_node_f += len(f_next_queue)
        queue_from_f = f_next_queue

        if snuke_bool:
            s_next_queue = set()
            for i in queue_from_s:
                next_point = edges[i]
                for point in next_point:
                    if point in queue_from_f:
                        visited_f[i] = True
                        snuke_bool = False
                        break

                    if visited_s[point]:
                        continue
                    else:
                        s_next_queue.add(point)
                        visited_s[point] = True

            queue_from_s = s_next_queue

    if n_node_f >= N // 2:
        ans = "Fennec"
    else:
        ans = "Snuke"

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

queue = collections.deque([1])
mf = [False] * (n+1)
count1 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != n:
            mf[node] = True
            count1 += 1
            queue.append(node)
queue = collections.deque([n])
mf = [False] * (n+1)
count2 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != 1:
            mf[node] = True
            count2 += 1
            queue.append(node)

if (count1+count2-(n-2)) % 2 ==1 :
    if count1 >= count2:
        print("Fennec")
    else:
        print("Snuke")
else:
   if count1 > count2:
        print("Fennec")
   else:
        print("Snuke")

Submission status: Wrong Answer

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

def dfs(v):
    d=[-1 for i in range(n)]
    q=[]
    d[v]=0
    q.append(v)
    while len(q):
        v=q.pop()
           
        for i in a[v]:
            if d[i]==-1:
                d[i]=d[v]+1
                q.append(i)
    return d
c1=dfs(0)
c2=dfs(n-1)
c=0
for i in range(n):
 if c1[i]>c2[i]:
    c+=1
if c>n/2:
  print("Snuke")
else:
  print("Fennec")

Submission status: Wrong Answer

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

queue = collections.deque([1])
mf = [False] * (n+1)
count1 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != n:
            mf[node] = True
            count1 += 1
            queue.append(node)
queue = collections.deque([n])
mf = [False] * (n+1)
count2 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != 1:
            mf[node] = True
            count2 += 1
            queue.append(node)

if (count1+count2-(n-2)) % 2 ==1 :
    flag = 1
else:
    flag = -1

if count1 + flag > count2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

queue = collections.deque([1])
mf = [False] * (n+1)
count1 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != n:
            mf[node] = True
            count1 += 1
            queue.append(node)
queue = collections.deque([n])
mf = [False] * (n+1)
count2 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != 1:
            mf[node] = True
            count2 += 1
            queue.append(node)

if (count1+count2-(n-2)) % 2 ==1 :
    flag = 1
else:
    flag = -1

if count1 + flag >= count2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

queue = collections.deque([1])
mf = [False] * (n+1)
count1 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != n:
            mf[node] = True
            count1 += 1
            queue.append(node)
queue = collections.deque([n])
mf = [False] * (n+1)
count2 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != 1:
            mf[node] = True
            count2 += 1
            queue.append(node)

if (count1+count2-(n-2)) % 2 ==1 :
    flag = 1
else:
    flag = 0

if count1 + flag >= count2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

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

queue = collections.deque([1])
mf = [False] * (n+1)
count1 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != n:
            mf[node] = True
            count1 += 1
            queue.append(node)
queue = collections.deque([n])
mf = [False] * (n+1)
count2 = 0
while queue:
    now = queue.popleft()
    for node in con[now]:
        if not mf[node] and node != 1:
            mf[node] = True
            count2 += 1
            queue.append(node)

if count1 >= count2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)

def find_path(now, par):
    if now == n - 1:
        path.append(n - 1)
        return True
    for to in g[now]:
        if to == par: continue
        if find_path(to, now):
            path.append(now)
            return True
    return False

def dfs1(now, par, color):
    color[now] = "b"
    for to in g[now]:
        if to == par: continue
        if color[to] == "w": continue
        dfs1(to, now, color)

def dfs2(now, par, color):
    color[now] = "w"
    for to in g[now]:
        if to == par: continue
        if color[to] == "b": continue
        dfs2(to, now, color)

n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b = map(int, raw_input().split())
    a -= 1; b -=1
    g[a].append(b)
    g[b].append(a)
path = []
find_path(0, -1)
path.reverse()
color = ["bl"] * n
color[0] = "b"
color[n - 1] = "w"
for i in xrange(1, len(path) - 1):
    v = path[i]
    if i % 2 == 1:
        color[v] = "b"
    else:
        color[v] = "w"
dfs1(0, -1, color)
dfs2(n - 1, -1, color)
cntf = 0
cnts = 0
for i in xrange(n):
    if color[i] == "b":
        cntf += 1
    else:
        cnts += 1
if cntf > cnts:
    print "Fennec"
else:
    print "Snuke"

Submission status: Wrong Answer

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

def dfs(v,vv):
    d=[-1 for i in range(n)]
    q=[]
    d[v]=0
    c=0
    q.append(v)
    while len(q):
        v=q.pop()
        if v!=vv:
           
         for i in a[v]:
            if d[i]==-1:
                d[i]=1
                c+=1
                q.append(i)
    return c
c1=dfs(0,n-1)
c2=dfs(n-1,0)
if c1>c2:
  print("Fennec")
else:
  print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)

def find_path(now, par):
    if now == n - 1:
        path.append(n - 1)
        return True
    for to in g[now]:
        if to == par: continue
        if find_path(to, now):
            path.append(now)
            return True
    return False

def dfs(now, par, color):
    color[now] = "b"
    for to in g[now]:
        if to == par: continue
        if color[to] == "w": continue
        dfs(to, now, color)

n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b = map(int, raw_input().split())
    a -= 1; b -=1
    g[a].append(b)
    g[b].append(a)
path = []
find_path(0, -1)
path.reverse()
color = ["bl"] * n
color[0] = "b"
color[n - 1] = "w"
for i in xrange(1, len(path) - 1):
    v = path[i]
    if i % 2 == 1:
        color[v] = "b"
    else:
        color[v] = "w"
dfs(0, -1, color)
cnt = 0
for i in xrange(n):
    if color[i] == "b":
        cnt += 1
if cnt > n - cnt:
    print "Fennec"
else:
    print "Snuke"

Submission status: Wrong Answer

Solution code:

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

def solve(N, Es):
    if N == 2:
        return "Snuke"
    path = find_path(N, 0, N - 1, Es)
    len_path = len(path)
    a = (len_path - 1)// 2
    b = a + 1
    p1 = path[a]
    p2 = path[b]
    e1 = count_edges(N, p1, p2, Es)
    e2 = N - e1
    if e1 > e2:
        return "Fennec"
    else:
        return "Snuke"

def find_path(N, s, g, Es):
    stack = [(s, 0)]
    path = [(s, 0)]
    visited = [False] * N
    visited[s] = True
    while True:
        v, d = stack.pop()
        if path[-1][1] == d:
            path.pop()
        path.append((v, d))
        for u in Es[v]:
            if visited[u]:
                continue
            stack.append((u, d + 1))
            if u == g:
                path = [p for p, depth in path] + [g]
                return path
        visited[v] = True

def count_edges(N, p1, p2, Es):
    stack = [p1]
    visited = [False] * N
    visited[p2] = True
    count = 0
    while stack:
        v = stack.pop()
        count += 1
        for u in Es[v]:
            if visited[u]:
                continue
            stack.append(u)
        visited[v] = True
    return count


N, Es = read_data()
print(solve(N, Es))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

cin = sys.stdin
# cin = open("in.txt", "r")

def line2N():
    return map(int, cin.readline().split())


N, = line2N()
adj = [[] for i in range(N+1)]
for i in range(N-1):
    u, v = line2N()
    adj[u].append(v)
    adj[v].append(u)

color = [0]*(N+1)
h_cnt = 1
t_cnt = 1
dq_head = deque([1])
color[1] = 1
dq_tail = deque([N])
color[N] = 1
for step in range(N):
    if step % 2==0:
        if not dq_head:
            t_cnt = N - h_cnt
            break
        u = dq_head.popleft()
        for v in adj[u]:
            if color[v]==0:
                color[v] = 1
                dq_head.append(v)
                h_cnt += 1
    else:
        if not dq_tail:
            h_cnt = N - t_cnt
            break
        u = dq_tail.popleft()
        for v in adj[u]:
            if color[v]==0:
                color[v] = 2
                dq_tail.append(v)
                t_cnt += 1

# print(h_cnt, t_cnt)
if h_cnt>t_cnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)

def find_path(now, par):
    if now == n - 1:
        path.append(n - 1)
        return True
    for to in g[now]:
        if to == par: continue
        if find_path(to, now):
            path.append(now)
            return True
    return False

def dfs(now, par, color):
    color[now] = 'b'
    for to in g[now]:
        if to == par: continue
        if color[to] == "w": continue
        dfs(to, now, color)

n = int(raw_input())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b = map(int, raw_input().split())
    a -= 1; b -=1
    g[a].append(b)
    g[b].append(a)
path = []
find_path(0, -1)
path.reverse()
color = ["bl"] * n
color[n - 1] = "w"
for i in xrange(1, len(path) - 1):
    v = path[i]
    if i % 2 == 1:
        color[v] = "b"
    else:
        color[v] = "w"
dfs(0, -1, color)
cnt = 0
for i in xrange(n):
    if color[i] == "b":
        cnt += 1
if cnt > n - cnt:
    print "Fennec"
else:
    print "Snuke"

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    n = int(input())
    adj_list = [[] for i in range(n)]
    for i in range(n - 1):
        a1, b1 = map(int, sys.stdin.readline().split())
        adj_list[a1 - 1].append(b1 - 1)
        adj_list[b1 - 1].append(a1 - 1)
    path = dfs(0, -1, adj_list, n)
    assert len(path) >= 2
    fpath = len(path) - len(path) // 2
    cut = set(path[fpath - 1:fpath + 1])
    f = dfs2(0, -1, adj_list, n, cut)
    s = dfs2(n - 1, -1, adj_list, n, cut)
    assert f + s == n
    print("Fennec" if f > s else "Snuke")

def dfs(now, prev, adj_list, n):
    if now == n - 1:
        return [now]
    for next in adj_list[now]:
        if next == prev:
            continue
        p = dfs(next, now, adj_list, n)
        if p is not None:
            return [now] + p

def dfs2(now, prev, adj_list, n, cut):
    size = 1
    for next in adj_list[now]:
        if next == prev:
            continue
        if {now, next} == cut:
            continue
        s = dfs2(next, now, adj_list, n, cut)
        size += s
    return size

if __name__ == "__main__":
    main()