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 functools import reduce
import math
from collections import deque
from collections import defaultdict

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)       
    f= 0
    s= 0
    
    q = deque()
    q.append(1)
    d_from_1 = [-1]*(N+1)
    d_from_1[1] = 0
    i = 1
    while q:
        next_node = q.popleft()
        for succ in d[next_node]:
            if d_from_1[succ] == -1:
                d_from_1[succ] = i
                q.append(succ)
        i += 1
        
    q = deque()
    q.append(N)
    d_from_N = [-1]*(N+1)
    d_from_N[N] = 0
    i = 1
    q.append(N)
    while q:
        next_node = q.popleft()
        for succ in d[next_node]:
            if d_from_N[succ] == -1:
                d_from_N[succ] = i
                q.append(succ)
        i += 1
    # print(d_from_1)
    # print(d_from_N)
    for i in range(1,N+1):
        if(d_from_1[i] < d_from_N[i]):
            f += 1
        else:
            s += 1
    if(f>s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math
from collections import deque
from collections import defaultdict

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)       
    f= 0
    s= 0
    
    q = deque()
    q.append(1)
    d_from_1 = [-1]*(N+1)
    i = 1
    while q:
        next_node = q.popleft()
        for succ in d[next_node]:
            if d_from_1[succ] == -1:
                d_from_1[succ] = i
                q.append(succ)
        i += 1
        
    q = deque()
    q.append(N)
    d_from_N = [-1]*(N+1)
    i = 1
    q.append(N)
    while q:
        next_node = q.popleft()
        for succ in d[next_node]:
            if d_from_N[succ] == -1:
                d_from_N[succ] = i
                q.append(succ)
        i += 1
    # print(d_from_1)
    # print(d_from_N)
    for i in range(1,N+1):
        if(d_from_1[i] <= d_from_N[i]):
            f +=1
        else:
            s += 1
    if(f>s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math
from collections import deque
from collections import defaultdict

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)       
    f= 0
    s= 0
    
    q = deque()
    q.append(1)
    d_from_1 = [-1]*(N+1)
    i = 1
    while q:
        next_node = q.popleft()
        for succ in d[next_node]:
            if d_from_1[succ] == -1:
                d_from_1[succ] = i
                q.append(succ)
        i += 1
        
    q = deque()
    q.append(N)
    d_from_N = [-1]*(N+1)
    i = 1
    q.append(N)
    while q:
        next_node = q.popleft()
        for succ in d[next_node]:
            if d_from_N[succ] == -1:
                d_from_N[succ] = i
                q.append(succ)
        i += 1
    # print(d_from_1)
    # print(d_from_N)
    for i in range(1,N+1):
        if(d_from_1[i] < d_from_N[i]):
            f +=1
        else:
            s += 1
    if(f>s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math
from collections import deque
from collections import defaultdict

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)
        
    bw = defaultdict(str)
    bw[1] = 'b'
    bw[N] = 'w'
    f= 0
    s= 0
    q = deque()
    q.append(1)
    q.append(N)
    while q:
        next_node = q.popleft()
        if(bw[next_node] == 'b'):
            f+=1
        elif(bw[next_node] == 'w'):
            s+=1
        for succ in d[next_node]:
            if bw[succ] == '':
                bw[succ] = bw[next_node]
                q.append(succ)
    if(f>=s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N=input()

nl=[ [] for i in range(N+1)]
D=[ 0 for i in range(N+1)]	# No.1からの距離
V=[ 0 for i in range(N+1)]	# 訪問済みフラグ

for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	nl[b].append(a)


def bfs(v):	#1からの頂点Nまでの距離を算出
	q = deque([]) 
	V[v]=1
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if V[i]==0:
				D[i]=D[v]+1
				V[i]=1
				q.append(i)

bfs(1)


L=deque([]) 	#1-Nまでの最短経路を復元 
def bfs2(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if D[i]==D[v]-1 and i!=1:
				q.append(i)
				L.appendleft(i)

bfs2(N)


color=[ None for i in range(N+1)]
color[1]="b"
color[N]="w"

l=len(L)
for i in range( (l+1)/2 ):
	color[ L[i] ]="b"

for i in range( (l+1)/2, l ):
	color[ L[i] ]="w"



def bfs3(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if color[i] is None:
				color[i]=color[v]
				q.append(i)
for i in L:
	bfs3(i)
		


b_cnt=color.count("b")
w_cnt=color.count("w")


if N%2==1:
	if b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"
else:
	if b_cnt==w_cnt:	
		print "Snuke"
	elif b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"

Submission status: Wrong Answer

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

N=input()

nl=[ [] for i in range(N+1)]
D=[ 0 for i in range(N+1)]	# No.1からの距離
V=[ 0 for i in range(N+1)]	# 訪問済みフラグ

for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	nl[b].append(a)


def bfs(v):	#1からの頂点Nまでの距離を算出
	q = deque([]) 
	V[v]=1
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if V[i]==0:
				D[i]=D[v]+1
				V[i]=1
				q.append(i)

bfs(1)


L=deque([]) 	#1-Nまでの最短経路を復元 
def bfs2(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if D[i]==D[v]-1 and i!=1:
				q.append(i)
				L.appendleft(i)

bfs2(N)


color=[ None for i in range(N+1)]
color[1]="b"
color[N]="w"

l=len(L)
for i in range( (l+1)/2 ):
	color[ L[i] ]="b"

for i in range( (l+1)/2, l ):
	color[ L[i] ]="w"

def bfs3(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if color[i] is None:
				color[i]=color[v]
				q.append(i)


bfs3(1)
bfs3(N)

b_cnt=color.count("b")
w_cnt=color.count("w")


if N%2==1:
	if b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"
else:
	if b_cnt==w_cnt:	
		print "Snuke"
	elif b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"

Submission status: Wrong Answer

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

N=input()

nl=[ [] for i in range(N+1)]
D=[ 0 for i in range(N+1)]	# No.1からの距離
V=[ 0 for i in range(N+1)]	# 訪問済みフラグ

for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	nl[b].append(a)


def bfs(v):
	q = deque([]) 
	V[v]=1
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if V[i]==0:
				D[i]=D[v]+1
				V[i]=1
				q.append(i)

bfs(1)


L=deque([]) 	#最短経路復元 1-N間
def bfs2(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if D[i]==D[v]-1 and i!=1:
				q.append(i)
				L.appendleft(i)

bfs2(N)

color=[ None for i in range(N+1)]
color[1]="b"
color[N]="w"


for i,x  in enumerate(L):
	if i%2==0:
		color[x]="b"
	else:
		color[x]="w"

def bfs3(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if color[i] is None:
				color[i]=color[v]
				q.append(i)



bfs3(1)
bfs3(N)

b_cnt=color.count("b")
w_cnt=color.count("w")

if N%2==1:
	if b_cnt>w_cnt+1:
		print "Fennec"
	else:		
		print "Snuke"
else:
	if b_cnt==w_cnt+1:	
		print "Snuke"
	elif b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
d = [0] * N
INF = float('inf')
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heapq.heappush(h, [d[e], e])

dijkstra(0)
d2 = d.copy()
F = d2

dijkstra(N - 1)
S = d

Fennec = 0
for i in range(N):
    if F[i] < S[i]:
        Fennec += 1
        
print('Fennec' if Fennec >= N - Fennec else 'Snuke')

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
d = [0] * N
INF = float('inf')
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heapq.heappush(h, [d[e], e])

dijkstra(0)
d2 = d.copy()
F = d2

dijkstra(N - 1)
S = d

Fennec = 0
for i in range(N):
    if F[i] < S[i]:
        Fennec += 1
        
print('Fennec' if Fennec > N - Fennec else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n=int(input())
a=[0]*(n+1)
b=[0]*(n+1)
vst=[0]*(n+1)
g=[[] for _ in range(n+1)]
for i in range(1,n):
    a[i],b[i]=map(int,input().split())
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])

def bfs(x):
    cnt=0
    q=deque()
    q.append(x)
    while len(q)>0:
        c=q.popleft()
        vst[c]=1
        for nb in g[c]:
            if vst[nb]!=1:
                q.append(nb)
    return vst

def dfs(x,y,path):
    path=deque(path)
    path.append(x)
    vst[x]=1
    if x==y:
        return path
    
    for i in g[x]:
        if vst[i]!=1:
            a=dfs(i,y,path)
            if a!=None:
                return a

r=dfs(1,n,deque())
rl=list(r)
t=(len(rl)-1)//2
g[rl[t]].remove(rl[t+1])
#print(rl)
vst=[0]*(n+1)
#print('Fennec' if len(bfs(1))>=n//2 else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n=int(input())
a=[0]*(n+1)
b=[0]*(n+1)
vst=[0]*(n+1)
g=[[] for _ in range(n+1)]
for i in range(1,n):
    a[i],b[i]=map(int,input().split())
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])

def bfs(x):
    cnt=0
    q=deque()
    q.append(x)
    while len(q)>0:
        c=q.popleft()
        vst[c]=1
        for nb in g[c]:
            if vst[nb]!=1:
                q.append(nb)
    return vst

def dfs(x,y,path):
    path=deque(path)
    path.append(x)
    vst[x]=1
    if x==y:
        return path
    
    for i in g[x]:
        if vst[i]!=1:
            a=dfs(i,y,path)
            if a!=None:
                return a

r=dfs(1,n,deque())
rl=list(r)
t=(len(rl)-1)//2
g[rl[t]].remove(rl[t+1])
#print(rl)
vst=[0]*(n+1)
print('Fennec' if len(bfs(1))>=n//2 else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n=int(input())
a=[0]*(n+1)
b=[0]*(n+1)
g=[[] for _ in range(n+1)]
for i in range(1,n):
    a[i],b[i]=map(int,input().split())
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])

def bfs(x):
    cnt=0
    q=deque()
    q.append(x)
    vst=set()
    while len(q)>0:
        c=q.popleft()
        vst.add(c)
        for nb in g[c]:
            if nb not in vst:
                q.append(nb)
    return vst

def dfs(x,y,path,vst):
    path=deque(path)
    vst=deque(vst)
    path.append(x)
    vst.append(x)
    if x==y:
        return path
    
    for i in g[x]:
        if i not in vst:
            a=dfs(i,y,path,vst)
            if a!=None:
                return a

r=dfs(1,n,deque(),deque())
rl=list(r)
t=(len(rl)-1)//2
g[rl[t]].remove(rl[t+1])
#print(rl)

print('Fennec' if len(bfs(1))>=n//2 else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
brack[N]=0
check=deque([1])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if brack[i]>10**9:
            brack[i]=brack[now]+1
            check.append(i)
white=[float('inf')]*(N+1)
white[N]=0
white[1]=0
check=deque([N])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if white[i]>10**9:
            white[i]=white[now]+1
            check.append(i)
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
brack[N]=0
check=deque([1])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if brack[i]>brack[now]+1:
            brack[i]=brack[now]+1
            check.append(i)
white=[float('inf')]*(N+1)
white[N]=0
white[1]=0
check=deque([N])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if white[i]>white[now]+1:
            white[i]=white[now]+1
            check.append(i)
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
m_dist = [float('inf') for _ in range(N)]
# 頂点0からの距離
# 0から近い方がFennec
# N-1から近い方がSnuke

e = [[] for _ in range(N)]
# 道, 隣接リスト, 0-indexed

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

q = deque()
q.append((0, 0, [0]))

# m_dist[v]:=頂点0からの最短距離
while q:
    v, d, p = q.popleft()
    if m_dist[v] <= d: continue
    m_dist[v] = d
    # min(m_dist[v], d)
    for nv in e[v]:
        q.append((nv, d + 1, p + [nv]))

Fennec_count = 0
for v in range(N):
    if m_dist[v] <= abs(m_dist[N - 1] - m_dist[v]):
        # 頂点0から近い場合
        # 等距離なら先に塗れる黒になる
        Fennec_count += 1
        # 黒

print('Fennec' if Fennec_count > N - Fennec_count else 'Snuke')

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 9)


def dfs_to_color(v, my_color):
    # 着色可能な範囲を着色する
    # 自分の色（黒、白）の幹から出ている未着色のマスが着色可能
    if m_bl[v]: return
    m_bl[v] = True
    if m[v] == (not my_color): return
    m[v] = my_color
    for nv in e[v]:
        dfs_to_color(nv, my_color)


N = int(input())
m = [None for _ in range(N)]
m[0] = True
m[N - 1] = False
# 色, 0-indexed
# True == 黒 == Fennec
# False == 白 == Snuke
m_dist = [float('inf') for _ in range(N)]
# 頂点0からの距離
m_bl = [False for _ in range(N)]
# 着色作業が完了したか

e = [[] for _ in range(N)]
# 道, 隣接リスト, 0-indexed

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

path = []
q = deque()
q.append((0, 0, [0]))

# 頂点(0, N - 1)間の最短経路pathを求める
# m_dist[v]:=頂点0からの最短距離
while True:
    v, d, p = q.popleft()
    if m_dist[v] <= d: continue
    m_dist[v] = d
    # min(m_dist[v], d)

    if v == N - 1:
        path = p
        break
    for nv in e[v]:
        q.append((nv, d + 1, p + [nv]))

for p in path:
    if m_dist[p] <= abs(m_dist[N - 1] - m_dist[p]):
        # 頂点0から近い場合
        # 等距離なら先に塗れる黒になる
        m[p] = True
        # 黒
    else:
        # 頂点N-1から近い場合
        m[p] = False
        # 白
# 最短経路を先に着色する

dfs_to_color(0, True)
# Fennec

dfs_to_color(N - 1, False)
# Snuke

print('Fennec' if m.count(True) > m.count(False) else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v, d, path):
    # 頂点(0, N - 1)間の最短距離を求める
    # m_dist[v]:=頂点0からの最短距離
    res = []
    if m_dist[v] < float('inf'):
        return
    m_dist[v] = min(m_dist[v], d)
    if v == N - 1:
        return path
    for nv in e[v]:
        ret = dfs(nv, d + 1, path + [nv])
        if ret:
            res = ret
            break
    return res


def dfs_to_color(v, my_color):
    # 着色可能な範囲を着色する
    # 自分の色（黒、白）の幹から出ている未着色のマスが着色可能
    if m_bl[v]: return
    m_bl[v] = True
    if m[v] == my_color or m[v] == None:
        m[v] = my_color
        for nv in e[v]:
            dfs_to_color(nv, my_color)


N = int(input())
m = [None for _ in range(N)]
m[0] = True
m[N - 1] = False
# 色, 0-indexed
# True == 黒 == Fennec
# False == 白 == Snuke
m_dist = [float('inf') for _ in range(N)]
# 頂点0からの距離
m_bl = [False for _ in range(N)]
# 着色作業が完了したか

e = [[] for _ in range(N)]
# 道, 隣接リスト, 0-indexed

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

path = dfs(0, 0, [0])
# 頂点(0, N - 1)間の最短距離をm_dist[N-1]に代入
# 最短パスを返す

for p in path:
    if m_dist[p] <= abs(m_dist[N - 1] - m_dist[p]):
        # 頂点0から近い場合
        # 等距離なら先に塗れる黒になる
        m[p] = True
        # 黒
    else:
        # 頂点N-1から近い場合
        m[p] = False
        # 白
# 最短経路を先に着色する

dfs_to_color(0, True)
# Fennec

dfs_to_color(N - 1, False)
# Snuke

print('Fennec' if m.count(True) > m.count(False) else 'Snuke')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
children = 0
ad = [{} for _ in range(N)]

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

def dfs(v=0,d=0):
    if v == N-1:
        global mid
        mid = d-1
        return
    if not ad[v]:
        global children
        children += d
    while ad[v]:
        key,nv = ad[v].popitem()
        ad[nv].pop(key)
        dfs(nv,d+1)
    
dfs()
f = children
s = N - (children+mid+2)
if mid%2: f += 1
player = ["Fennec","Snuke"]
ans = player[0] if f > s else player[1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
mid = -1
children = 0
ad = [{} for _ in range(N)]

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

def dfs(v=0,d=0):
    if v == N-1:
        global mid
        mid = d-1
        return
    if not ad[v]:
        global children
        children += d
    while ad[v]:
        key,nv = ad[v].popitem()
        ad[nv].pop(key)
        dfs(nv,d+1)
    
dfs()
f = children
s = N - (children+mid+2)
if mid%2: f += 1
player = ["Fennec","Snuke"]
ans = player[0] if f > s else player[1]
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
f_bfs_map = [0 for i in range(n)]
q = deque()
q.append(0)
f_bfs_map[0] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != n-1 and not f_bfs_map[y]:
            f_bfs_map[y] = 1
            q.append(y)
s = sum(f_bfs_map)
s_bfs_map = [0 for i in range(n)]
q = deque()
q.append(n-1)
s_bfs_map[n-1] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != 0 and not s_bfs_map[y]:
            s_bfs_map[y] = 1
            q.append(y)
s += sum(s_bfs_map)
s -= n
f_su = sum(f_bfs_map)-1-s+s//2+s%2
s_su = sum(s_bfs_map)-1-s+s//2
if f_su > s_su:
    print(s)
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
f_bfs_map = [0 for i in range(n)]
q = deque()
q.append(0)
f_bfs_map[0] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != n-1 and not f_bfs_map[y]:
            f_bfs_map[y] = 1
            q.append(y)
s = sum(f_bfs_map)
s_bfs_map = [0 for i in range(n)]
q = deque()
q.append(n-1)
s_bfs_map[n-1] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != 0 and not s_bfs_map[y]:
            s_bfs_map[y] = 1
            q.append(y)
s += sum(s_bfs_map)
s -= n
f_su = sum(f_bfs_map)-1-s+s//2+s%2
s_su = sum(s_bfs_map)-1-s+s//2
if f_su > s_su:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
f_bfs_map = [0 for i in range(n)]
q = deque()
q.append(0)
f_bfs_map[0] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != n-1 and not f_bfs_map[y]:
            f_bfs_map[y] = 1
            q.append(y)
s = sum(f_bfs_map)
s_bfs_map = [0 for i in range(n)]
q = deque()
q.append(n-1)
s_bfs_map[n-1] = 1
while q:
    x = q.pop()
    for y in v[x]:
        if y != 0 and not s_bfs_map[y]:
            s_bfs_map[y] = 1
            q.append(y)
s += sum(s_bfs_map)
s -= n
f_su = sum(f_bfs_map)-1-s//2+s%2
s_su = sum(s_bfs_map)-1-s//2
if f_su > s_su:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T