/*
   Prints state expansions at time t for a FSA. Starts with 1 token in state 0.


maxtime
stateNum
4  5  (means and edge from 4 to 5)
3  6
-1

*/

#include<stdio.h>
#include<gmp.h>

#define MAX_EDGES 10000
#define MAX_STATES 100


int states[MAX_STATES][MAX_EDGES];
int edges[MAX_STATES];
mpz_t SUMS[MAX_STATES];
mpz_t NEW_SUMS[MAX_STATES];
mpz_t SUM;
int maxTime;
int stateNum;
int edgeNum;


int main()
{
  int i,j,k;

  for(i=0;i<MAX_STATES;i++)
    {
      mpz_init(SUMS[i]);
      mpz_init(NEW_SUMS[i]);
      mpz_set_ui(SUMS[i],0);
      edges[i]=0;
    }
  mpz_init(SUM);
  mpz_set_ui(SUMS[0],1);

  gmp_scanf("%d",&maxTime);
  gmp_scanf("%d",&stateNum);
  //gmp_scanf("%d",&edgeNum);
  
  for(i=0;i<1000000;i++)
    {
      gmp_scanf("%d",&j);
      if(j<0)
	break;
      gmp_scanf("%d",&k);
      states[j][edges[j]]=k;
      edges[j]++;
    }
  gmp_printf("1\n");
  for(i=0;i<maxTime;i++)
    {
      for(j=0;j<stateNum;j++)
	  mpz_set_ui(NEW_SUMS[j],0);
      for(j=0;j<stateNum;j++)
	{
	  for(k=0;k<edges[j];k++)
	    mpz_add(NEW_SUMS[states[j][k]],
		    NEW_SUMS[states[j][k]],
		    SUMS[j]);
	}
      for(j=0;j<stateNum;j++)
	mpz_set(SUMS[j],NEW_SUMS[j]);
      
      mpz_set_ui(SUM,0);
      for(j=0;j<stateNum;j++)
	mpz_add(SUM,SUM,SUMS[j]);
      gmp_printf("%Zd\n",SUM);
       
    }


}