n = gets.to_i
m = gets.to_i

E = Hash.new {|h,k|
	h[k] = Array.new
}

m.times {
	a,b = gets.split.map(&:to_i)
	E[a] << b
}


L = []
def visit(node,visited)
	unless visited[node]
		visited[node] = true
		E[node].each {|n|
			visit(n,visited)
		}
		L << node
	end
end

t = {}
(1..n).each {|x|
	visit(x,t)
}
L.reverse!
b = L.each_cons(2).all? {|a,b|
	E[a].include? b
}
puts L * "\n"
puts b ? 0 : 1