#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main()
{
int m[100];
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++)
{
vector <string>::const_iterator si;
int fr=2;
cin >> s1 >> s2;
if(j>0)
{

for(si=s.begin();si!=s.end();si++)
if((*si==s1)||(*si==s2))
{
int pos=std::find(si.begin(),si.end(),s1)-si.begin();
fr+=m[pos/2];
}
}
s.push_back(s1);
s.push_back(s2);
m[j]=fr-1;
printf("%d\n",fr);
}
}
return 0;
}