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