#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main()
{
int k=0;;
vector <string> s;
string s1,s2;
int testcase,i,j;
long int n;
scanf("%d",&testcase);
scanf("%ld",&n);
for(i=0;i<testcase;i++)
{
for(j=0;j<n;j++)
{
k=0;
int fr=2;
cin >> s1 >> s2;
if(j>0)
{
vector <string>::iterator si;
for(si=s.begin();si!=s.end();si++)
{
k++;
if((*si==s1)||(*si==s2))
fr+=m[k];
s.push_back(s1);
s.push_back(s2);
m[j]=fr-1;
printf("%d\n",fr);
}
}
return 0;
}