n=gets.to_i
m=gets.to_i
w=(0..n).map{[]}
r=[0]*(n+1)
$<.map{|o|i,j=o.split.map(&:to_i);w[i]<<j}

a=[]
s=(1..n).to_a
p=w.flatten.uniq
c=0
while p !=[]
t=s-p
c=1 if t.size>1
t.map{|i|p-=w[i]}
a+=t
s-=t
end
p (*(a+s),c)

#t=(1..n).to_a-w.flatten
#c=0
#while t!=[]
#c+=1
#t=t.flat_map{|i|r[i]=c;w[i]}.uniq
#end
#p *(1..n).sort_by{|i|r[i]},c<n ?1:0