Problem p03660 (python)

Fixed submission:
#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append([b,1])
    else:
        d[a]=[[b,1]]
    if b in d.keys():
        d[b].append([a,1])
    else:
        d[b]=[[a,1]]
        
x=DIJKSTRA(1,d)[1:]
y=DIJKSTRA(n,d)[1:]
#print(x)
#print(y)
F=0
S=0
for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1
if F<=S:
    print("Snuke")
else:
    print("Fennec")

Buggy submission (verdict: Runtime Error):
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=[]
    Q.append_left((0,point))
    
    while Q:
        c,p=Q.pop()
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                Q.append_left((c+1,np))
    return cost

n=int(input())
d=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

if F<=S:
    print("Snuke")
else:
    print("Fennec")

Buggy submission (verdict: Runtime Error):
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=[]
    Q.appendleft((0,point))
    
    while Q:
        c,p=Q.pop()
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                heappush(Q,(c+1,np))
    return cost

n=int(input())
d=[deque()for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

if F<=S:
    print("Snuke")
else:
    print("Fennec")

Buggy submission (verdict: Runtime Error):
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1]*(n+1)
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    preference= [None]*(n+1)#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while Q:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

n=int(input())
d=defaultdict(list)

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

x,y=DIJKSTRA(n,d)
#print(x,y)
point=1
pre=[1]
while point!=n:
    point=x[point]
    pre.append(point)
#print(pre)

if len(pre)%2==0:
    l.remove([pre[len(pre)//2-1],pre[len(pre)//2]])
else:
    l.remove([pre[len(pre)//2],pre[len(pre)//2+1]])
#print(l)
u=UNION_FIND(n+1)

for k,v in l:
    u.union(k,v)
if u.size(1)>u.size(n):
    print("Fennec")
else:
    print("Snuke")

Buggy submission (verdict: Runtime Error):
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1]*(n+1)
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    preference= [None]*(n+1)#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while Q:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

n=int(input())
d=defaultdict(list)

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

x,y=DIJKSTRA(n,d)
#print(x,y)
point=1
pre=[1]
while point!=n:
    point=x[point]
    pre.append(point)
#print(pre)

if len(pre)%2==0:
    l.remove([pre[len(pre)//2-1],pre[len(pre)//2]])
else:
    l.remove([pre[len(pre)//2],pre[len(pre)//2+1]])
#print(l)
u=UNION_FIND(n+1)

for k,v in l:
    u.union(k,v)
if u.size(1)>u.size(n):
    print("Fennec")
else:
    print("Sunuke")

Buggy submission (verdict: Runtime Error):
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1]*(n+1)
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    preference= [None]*(n+1)#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while Q:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

n=int(input())
d=defaultdict(list)

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

x,y=DIJKSTRA(n,d)
#print(x,y)
point=1
pre=[1]
while point!=n:
    point=x[point]
    pre.append(point)
#print(pre)

if len(pre)%2==0:
    l.remove([pre[len(pre)//2-1],pre[len(pre)//2]])
else:
    l.remove([pre[len(pre)//2],pre[len(pre)//2+1]])
#print(l)
u=UNION_FIND(n+1)

for k,v in l:
    u.union(k,v)
if u.size(1)>u.size(n):
    print("Sunuke")
else:
    print("Fennec")

Buggy submission (verdict: Runtime Error):
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1]*(n+1)
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
    
    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
        
def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    preference= [None]*(n+1)#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while Q:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

n=int(input())
d=defaultdict(list)

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

x,y=DIJKSTRA(n,d)
if x[1]!=n:
    point=1
    pre=[1]
#    print(x,y)
    while point!=n:
        pre.append(x[point])
        point=x[x[point]]
    pre.append(point)
else:
    pre=[1,n]


if len(pre)%2:
    try:
        l.remove((pre[len(pre)//2],pre[len(pre)//2+1]))
    except:
        l.remove((pre[len(pre)//2+1],pre[len(pre)//2]))
else:
    try:
        l.remove((pre[len(pre)//2-1],pre[len(pre)//2]))
    except:
        l.remove((pre[len(pre)//2],pre[len(pre)//2-1]))
u=UNION_FIND(n+1)
for k,v in l:
    u.union(k,v)
if u.size(1)>u.size(n):
    print("Fennec")
else:
    print("Snuke")