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 queue import deque

n = int(input())
li = [[] for _ in range(n+1)]

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

def width_prime(start,li,n):
    inf = 10**10
    visited = [False]*(n+1)
    length = [inf]*(n+1)
    length[start] = 0
    visited[start] = True
    work_queue = deque([])
    work_queue.append(start)
    while work_queue:
        now = work_queue.popleft()
        visited[now] = True
        for i in li[now]:
            if visited[i]:
                continue
            work_queue.append(i)
            visited[i] = True
            if length[i] > length[now]+1:
                length[i] = length[now]+1
    return length

le_fe = width_prime(1,li,n)
le_su = width_prime(n,li,n)

su = 0
fe = 0
for i in range(1,n+1):
    if le_fe[i] <= le_su[i]:
        fe += 1
    else:
        su += 1

if fe > su:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
from queue import deque

n = int(input())
li = [[] for _ in range(n+1)]

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

def width_prime(start,li,n):
    inf = 10**10
    visited = [False]*(n+1)
    length = [inf]*(n+1)
    length[start] = 0
    visited[start] = True
    work_queue = deque([])
    work_queue.append(start)
    while work_queue:
        now = work_queue.popleft()
        visited[now] = True
        for i in li[now]:
            if visited[i]:
                continue
            work_queue.append(i)
            visited[i] = True
            if length[i] > length[now]+1:
                length[i] = length[now]+1
    return length

le_fe = width_prime(1,li,n)
le_su = width_prime(n,li,n)

print(le_su)
print(le_fe)

su = 0
fe = 0
for i in range(1,n+1):
    if le_fe[i] <= le_su[i]:
        fe += 1
    else:
        su += 1

if fe > su:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
from queue import deque

n = int(input())
li = [[] for _ in range(n+1)]

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

def width_prime(start,li,n):
    inf = 10**10
    visited = [False]*(n+1)
    length = [inf]*(n+1)
    length[start] = 0
    visited[start] = True
    work_queue = deque([])
    work_queue.append(start)
    while work_queue:
        now = work_queue.popleft()
        visited[now] = True
        for i in li[now]:
            if visited[i]:
                continue
            work_queue.append(i)
            visited[i] = True
            if length[i] > length[now]+1:
                length[i] = length[now]+1
    return length

le_fe = width_prime(1,li,n)
le_su = width_prime(n,li,n)

su = 0
fe = 0
for i in range(1,n+1):
    if le_fe[i] <= le_su[i]:
        fe += 1
    else:
        su += 1

if fe >= su:
    print("Fennec")
else:
    print("Sunuke")

Submission status: Wrong Answer

Solution code:
N=int(input())
D=[[] for i in range(N)]
F=[0]*N
S=[0]*N
for i in range(N-1):
  a,b=map(int, input().split())
  a-=1
  b-=1
  D[a].append(b)
  D[b].append(a)
 
from collections import deque
import sys
sys.setrecursionlimit(10**7) 

def bfsF(n):
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if i!=N-1 and F[i]==0:
        F[i]=1
        q.append(i)
F[0]=1
bfsF(0)
        
def bfsS(n):
  qq=deque()
  qq.append(n)
  while len(qq):
    x=qq.popleft()
    for i in D[x]:
      if i!=0 and S[i]==0:
        S[i]=-1
        qq.append(i)

S[N-1]=-1
bfsS(N-1)
  
pcnt,mcnt,zcnt=0,0,0
for i in range(N):
  if F[i]+S[i]==0:
    zcnt+=1
  elif F[i]+S[i]==1:
    pcnt+=1
  else:
    mcnt+=1
ff,ss=0,0
if zcnt%2==1:
  ff+=1
if ff+pcnt>ss+mcnt:
  print('Fennec')
else:
  print('Snuke')

Submission status: Wrong Answer

Solution code:
N=int(input())
D=[[] for i in range(N)]
F=[0]*N
S=[0]*N
for i in range(N-1):
  a,b=map(int, input().split())
  a-=1
  b-=1
  D[a].append(b)
  D[b].append(a)
 
from collections import deque
import sys
sys.setrecursionlimit(10**7) 

def bfsF(n):
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if i!=N-1 and F[i]==0:
        F[i]=1
        q.append(i)
        
def bfsS(n):
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if i!=0 and S[i]==0:
        S[i]=-1
        q.append(i)
F[0]=1
S[N-1]=-1
bfsF(0)
bfsS(N-1)
  
pcnt,mcnt,zcnt=0,0,0
for i in range(N):
  if F[i]+S[i]==0:
    zcnt+=1
  elif F[i]+S[i]==1:
    pcnt+=1
  else:
    mcnt+=1
ff,ss=0,0
if zcnt%2==1:
  ff+=1
if ff+pcnt>ss+mcnt:
  print('Fennec')
else:
  print('Snuke')

Submission status: Wrong Answer

Solution code:
N=int(input())
D=[[] for i in range(N)]
F=[0]*N
S=[0]*N
for i in range(N-1):
  a,b=map(int, input().split())
  a-=1
  b-=1
  D[a].append(b)
  D[b].append(a)
 
from collections import deque
import sys
sys.setrecursionlimit(10**7) 

def bfsF(n,p):
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if i!=p and i!=N-1 and F[i]==0:
        F[i]=1
        q.append(i)
        
def bfsS(n,p):
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if i!=p and i!=0 and S[i]==0:
        S[i]=-1
        q.append(i)
bfsF(0,-1)
bfsS(N-1,-1)
F[0]=1
S[N-1]=-1
  
pcnt,mcnt,zcnt=0,0,0
for i in range(N):
  if F[i]+S[i]==0:
    zcnt+=1
  elif F[i]+S[i]==1:
    pcnt+=1
  else:
    mcnt+=1
ff,ss=zcnt//2,zcnt//2
if zcnt%2==1:
  ff+=1
if ff+pcnt<=ss+mcnt:
  print('Snuke')
else:
  print('Fennec')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq
INF = 10**6


def dijkstra(N, adj_nodes, start_node, non_use_node=None):
    assert start_node != non_use_node
    parent_nodes = [i for i in range(N)]
    d = [INF for _ in range(N)]
    d[start_node] = 0
    frontier = [(0, start_node)]
    while len(frontier) > 0:
        dist, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if next_node == non_use_node:
                continue
            if d[next_node] > dist + 1:
                d[next_node] = dist + 1
                parent_nodes[next_node] = node
                heapq.heappush(frontier, (d[next_node], next_node))
    return d, parent_nodes


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    fen_node, snu_node = 0, N - 1
    d, parent_nodes = dijkstra(N, adj_nodes, fen_node)
    n_bet = d[snu_node] - 1  # number of nodes between 1 and N
    adj_snu_node = parent_nodes[snu_node]
    adj_fen_node = snu_node
    while parent_nodes[adj_fen_node] != fen_node:
        adj_fen_node = parent_nodes[adj_fen_node]
    # calculate number of nodes in fennec side area
    d, _ = dijkstra(N, adj_nodes, fen_node, adj_fen_node)
    n_fen = len(list(filter(lambda x: x < N, d))) - 1
    n_fen += (n_bet + 1) // 2
    # calculate number of nodes in sunuke side area
    d, _ = dijkstra(N, adj_nodes, snu_node, adj_snu_node)
    n_snu = len(list(filter(lambda x: x < N, d))) - 1
    n_snu += n_bet // 2
    # answer
    if n_fen <= n_snu:
        print('Snuke')
    else:
        print('Fennec')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq
INF = 10**6


def dijkstra(N, adj_nodes, start_node, non_use_node=None):
    assert start_node != non_use_node
    parent_nodes = [i for i in range(N)]
    d = [INF for _ in range(N)]
    d[start_node] = 0
    frontier = [(0, start_node)]
    while len(frontier) > 0:
        dist, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if next_node == non_use_node:
                continue
            if d[next_node] > dist + 1:
                d[next_node] = dist + 1
                parent_nodes[next_node] = node
                heapq.heappush(frontier, (d[next_node], next_node))
    return d, parent_nodes


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    fen_node, snu_node = 0, N - 1
    d, parent_nodes = dijkstra(N, adj_nodes, fen_node)
    n_bet = d[snu_node] - 1  # number of nodes between 1 and N
    adj_snu_node = parent_nodes[snu_node]
    adj_fen_node = snu_node
    while parent_nodes[adj_fen_node] != fen_node:
        adj_fen_node = parent_nodes[adj_fen_node]
    # calculate number of nodes in fennec side area
    d, _ = dijkstra(N, adj_nodes, fen_node, adj_fen_node)
    n_fen = len(list(filter(lambda x: x < INF, d))) - 1
    n_fen += (n_bet + 1) // 2
    # calculate number of nodes in sunuke side area
    d, _ = dijkstra(N, adj_nodes, snu_node, adj_snu_node)
    n_snu = len(list(filter(lambda x: x < INF, d))) - 1
    n_snu += n_bet // 2
    # answer
    if n_fen <= n_snu:
        print('Snuke')
    else:
        print('Fennec')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    # https://atcoder.jp/contests/abc070/tasks/abc070_d
    # https://atcoder.jp/contests/abc070/submissions/11681543
    from heapq import heapify, heappop, heappush

    inf = 10 ** 17

    def dijkstra_heap(start, edge):
        # 始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        # a:重み(//), b:次の頂点(%)
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)

        while len(edgelist):
            # まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d

    # N:頂点数 W:辺数
    N = int(input())
    W = N-1

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

    fen = dijkstra_heap(0, edge)
    sun = dijkstra_heap(N-1, edge)
    f = 0
    s = 0

    for i in range(1, N-1):
        if fen[i] < sun[i]:
            f += 1
        elif fen[i] > sun[i]:
            s += 1
    print('Fennec' if f > s else 'Snuke')


resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    # https://atcoder.jp/contests/abc070/tasks/abc070_d
    # https://atcoder.jp/contests/abc070/submissions/11681543
    from heapq import heapify, heappop, heappush

    inf = 10 ** 17

    def dijkstra_heap(start, edge):
        # 始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        # a:重み(//), b:次の頂点(%)
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)

        while len(edgelist):
            # まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d

    # N:頂点数 W:辺数
    N = int(input())
    W = N-1

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

    fen = dijkstra_heap(0, edge)
    sun = dijkstra_heap(N-1, edge)
    f = 0
    s = 0

    for i in range(1, N-1):
        if fen[i] < sun[i]:
            f += 1
        elif fen[i] > sun[i]:
            s += 1
    print('Fennec' if f >= s else 'Snuke')


resolve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
V = defaultdict(list)

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

def dfs(source):
    dist = [0]*(N+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]:continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

d1 = dfs(1)
print("Fennec" if d1[N]%2==0 else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
V = defaultdict(list)

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

def dfs(source):
    dist = [0]*(N+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]:continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

d1, d2 = dfs(1), dfs(N)
print("Fennec" if any((d1[i]+d2[i])%2==0 for i in V[1]) else "Snuke")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
V = defaultdict(list)

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

def dfs(source):
    dist = [0]*(N+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]:continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

d1, d2 = dfs(1), dfs(N)
print("Fennec" if any(abs(d1[i]-d2[i])%2==0 for i in V[1]) else "Snuke")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(edges, n_nodes):
    visited = [None] * n_nodes
    visited[0] = "B"
    visited[-1] = "W"

    q = deque([0, n_nodes - 1])

    while q:
        i = q.popleft()

        for j in edges[i]:
            if visited[j] is None:
                print(i, j)
                visited[j] = visited[i]
                q.append(j)

    return visited


def main():
    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)

    visited = bfs(edges, N)
    if visited.count("B") > visited.count("W"):
        print("Fennec")
    else:
        print("Snuke")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b=map(int1,input().split())
        edge[a].append(b)
        edge[b].append(a)
    cost=[INF]*N
    cost[0]=0
    stack=[0]
    while stack:
        v=stack.pop()
        for nv in edge[v]:
            if cost[nv]==INF:
                cost[nv]=cost[v]+1
                stack.append(nv)
                if nv==N-1:
                    break
    d=cost[N-1]
    v=N-1
    for i in range(d//2+1):
        for nv in edge[v]:
            if cost[nv]==cost[v]-1:
                v=nv
                if i==d//2-1:
                    s=nv
                elif i==d//2:
                    f=nv
    if d//2==0:
        s=N-1

    class UnionFind:
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    
    stack=[s]
    used=[False]*N
    c=0
    while stack:
        v=stack.pop()
        used[v]=True
        c+=1
        for nv in edge[v]:
            if not used[nv] and nv!=f:
                stack.append(nv)
    if c>=N-c:
        print('Snuke')
    else:
        print('Fennec')
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
ab = [[] for i in range(n)]

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

fnc = deque()
snk = deque()

fnc.appendleft(0)
snk.appendleft(n-1)

check = [0]*(n)

check[0] = 1
check[n-1] = 1

while len(fnc) > 0 or len(snk) > 0:
    for i in range(len(fnc)):
        tmp = fnc.popleft()
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                check[ab[tmp][j]] = 1
                fnc.append(ab[tmp][j])
                
    if len(fnc) == 0:
        print('Snuke')
        exit()
                
    for i in range(len(snk)):
        tmp = snk.popleft()
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                check[ab[tmp][j]] = 1
                snk.append(ab[tmp][j])
                
    if len(snk) == 0:
        print('Fennec')
        exit()
    #fnc.popleft()
    #snk.popleft()

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(v, N):
    dist = [-1 for _ in range(N)]
    que = deque()
    que.append((v, 0, -1))
    while que:
        (now, cost, par) = que.popleft()
        dist[now] = cost
        for edge in edges[now]:
            if edge == par:
                continue
            que.append((edge, cost + 1, now))
    return dist


N = int(input())
edges = {i: [] for i 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)

dist_from_one = bfs(0, N)
dist_from_N = bfs(N - 1, N)
fennec = 0
for i in range(N):
    fennec += int(dist_from_one[i] <= dist_from_N[i])

print('Fennec' if fennec * 2 >= N else 'Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
node = [[] for _ in range(n)]

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

not_yet = deque(node[0])
dist = [0]*n
par = [0]*n
for v in node[0]:
  dist[v] = 1
  par[v] = 0

while not_yet:
  key = not_yet.popleft()
  for v in node[key]:
    if dist[v] or v == 0:
      continue
    dist[v] = dist[key]+1
    par[v] = key
    not_yet.append(v)

k = n-1
for _ in range((dist[n-1]-1)//2+1):
  k = par[k]

ans = 0
not_yet = deque([])
already = [False]*n
already[0] = True
already[k] = True
already[n-1] = True
for v in node[0]:
  if already[v]:
    continue
  ans += 1
  not_yet.append(v)
  already[v] = True
while not_yet:
  key = not_yet.popleft()
  for v in node[key]:
    if already[v]:
      continue
    ans += 1
    not_yet.append(v)
    already[v] = True

judge = (n-2)//2+1
if ans >= judge:
  print("Fennec")
else:
  print("Snuke")