Submission #44587799

---

Source Code Expand

N,M = gets.split.map(&:to_i)
ABCE = (1..M).map{|e|
	a,b,c = gets.split
 	next a.to_i-1,b.to_i-1,c,e
}
S = gets

Eoo = []
Eox = Hash.new{|h,x| h[x] = [] }
Exx = []
ABCE.each{|a,b,c,e|
	if S[a]==c && S[b]==c
		Eoo<<[a,b,e]
	elsif S[a]==c
		Eox[b]<<[a,b,e]
	elsif S[b]==c
		Eox[a]<<[b,a,e]
	else
		Exx<<[a,b,e]
	end
}

E = []
G = [-1]*N
F = lambda{|a|
	G[a]<0 ? a : G[a] = F[G[a]]
}
U = lambda{|a,b|
	a,b = F[a],F[b]
	next if a==b
	a,b = b,a if G[b]<G[a]
	G[a] += G[b]
	G[b] = a
	next true
}
Eoo.each{|a,b,e|
	E<<e if U[a,b]
}

V1,*Q = {}
G.each_with_index{|g,v|
	if g==-1
		V1[v] = v
	else
		Q.concat Eox[v]
	end
}
while (a,b,e = Q.pop)
	if V1[a] && U[a,b]
		E<<e
		V1.delete a
		Q.concat Eox[a]
	end
end
unless V1.empty?
	puts 'No'
#warn E*' '
	exit
end
Exx.each{|a,b,e|
	E<<e if U[a,b]
}
Eox.values.each{|abes|
	abes.each{|a,b,e|
		E<<e if U[a,b]
	}
}
puts 'Yes',E*' '

Submission Info

Judge Result