(N,M,T),*Y=$<.map{|l|l.split.map &:to_i};X=Y.reverse;$><<(T<2?(a=(r=0..N).map{|i|1<<i-1};Y.each{|x,y|a[x]=a[y]|=a[x]};g=r.find{|i|a[i]>2**N-2})?(o=[p]*-~N;o[g]=1;X.map{|x,y|o[x]?o[y]=?^:(o[x]||=o[y];?v)}):[-1]:N<3?[-1]:X.map{|x,y|y<4&&Y[x]==Y[6-x-y]?(Y[x]=Y[y];?v):(Y[y]=Y[x];?^)}).reverse.join