提出 #29479636

---

ソースコード 拡げる

def no!; p(-1); exit end

(N,M),D,*AB = $<.map{|ln| ln.split.map(&:to_i) }
D.unshift 0

G = [-1]*(N+1)
F = lambda{|a|
	G[a]<0 ? a : G[a] = F[G[a]]
}
U = lambda{|a,b|
	a,b = F[a],F[b]
	next true if a==b
	a,b = b,a if G[b]<G[a]
	G[a] += G[b]
	G[b] = a
	next false
}
AB.each{|a,b|
	no! if 0>D[a] -= 1
	no! if 0>D[b] -= 1
	no! if U[a,b]
}

Vg = (1..N).group_by(&F).map{|_,as| as.flat_map{|a| [a]*D[a] } }
Vg.sort_by!(&:size)
no! if Vg.size!=N-M || Vg[0].empty?

A = []
while as = Vg.pop
	bs = Vg[0]
	no! if ! bs || bs.size!=1
	A<<"#{as.pop} #{bs.pop}"
	next Vg.shift if as.empty?

	while 1<as.size
		Vg.shift
		bs = Vg[0]
		no! if ! bs || bs.size!=1
		A<<"#{as.pop} #{bs.pop}"
	end
	Vg[0] = as
end

puts A

提出情報

ジャッジ結果