import itertools
valjundeid, dioode=[int(s) for s in input().split(" ")]
k=itertools.product([0, 1], repeat=valjundeid)
dioodid=[]
for loendur in range(dioode):
  dioodid.append([int(s)-1 for s in input().split(" ")])
eraldi=[]
for komb in k:
  polevad=[]
  print(komb)
  for diood in dioodid:
     if komb[diood[0]]==1 and komb[diood[1]]==0:
        print(diood)
        polevad.append(diood)
  if(len(polevad)==1):
    eraldi.append(polevad[0])
print(eraldi)
for diood in dioodid:
   if diood in eraldi:
      print("jah")
   else:
      print("ei")