for(r=readline;m=[p,n]=r().split(S=' ');print(o))for(i=t=o='';i<n?m[i++]=r().split(S):++t<n?o+=t+~f(c=0,p)?S+c:c:0;)function f(s,p,i){for(i in p?m[s]:s-t||c++)+m[s][i]&&f(i,p-1)}