Submission #43935918

---

Source Code Expand

(N,M),*AB = $<.map{|ln| ln.split.map(&:to_i) }
E = Array.new(N+1){[]}
AB.each{|a,b|
	E[a]<<b
}
J = lambda{|ps|
	a,*as = ps[0]
	until a==as[0]
		as<<a
		bs = E[a].select{|b| ps.index b }
		break as.clear if bs.size!=1
		a, = bs
	end
	if as.size!=ps.size
		warn "NO (#{as.size}/#{ps.size})"
		warn as.inspect
		warn ps.map{|a|
			[a,E[a].select{|b| ps.index b }]
		}.to_h.inspect
	else
		warn 'YES'
	end
}
D = [nil]*(N+1)
F = lambda{|a,ps=[],vs={}|
	if vs[a]
		ps.shift(vs[a]).each{|b| vs.delete b }
		next true
	elsif ! D[a]
		D[a] = a
		vs[a] = ps.size
		ps<<a
		if E[a].any?{|b|
			F[b,ps,vs]
		} then
			next true
		else
			vs.delete a
			ps.pop
			next
		end
	else
	end
}
C = lambda{|ps|
	qs = []
	while a = ps.shift
		qs<<a
		if i = E[a].filter_map{|b| qs.index b }.max
			qs.shift i
			break
		end
		if i = E[a].filter_map{|b| ps.index b }.max
			ps.shift i
		end
	end
	next qs
}
(1..N).each{|a|
	ps = []
	if F[a,ps]
		ps = C[ps]
#		J[ps]
		puts ps.size,ps
		exit
	end
}
p~0

Submission Info

Judge Result