f=*r=0..100
$<.drop(2).map{|l|x,y=l.split.map &:to_i;f[x],f[y]=f[y],f[x]}
p r.map{|k|a=k;f.index{k==a=f[a]}+1}.reduce &:lcm