1 //用map把字符串转化为数字。初始化时初始2*n个会超时。
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<map>
 6 using namespace std;
 7 int t,n;
 8 int num[100005],fat[100005];
 9 map<string,int>m;
10 int find(int x)
11 {
12     int rt=x;
13     while(fat[rt]!=rt)
14     {
15         rt=fat[rt];
16     }
17     int i=x,j;
18     while(i!=rt)
19     {
20         j=fat[i];
21         fat[i]=rt;
22         i=j;
23     }
24     return rt;
25 }
26 void connect(int x,int y)
27 {
28     int xx=find(x),yy=find(y);
29     if(xx!=yy)
30     {
31         fat[xx]=yy;
32         num[yy]+=num[xx];
33         printf("%d\n",num[yy]);
34     }
35     else printf("%d\n",num[yy]);
36 }
37 int main()
38 {
39     char ch1[25],ch2[25];
40     while(scanf("%d",&t)!=EOF)
41     {
42         while(t--)
43         {
44             scanf("%d%d",&n);
45             for(int i=0;i<=100000;i++)   //开大了会超时
46             {
47                 fat[i]=i;
48                 num[i]=1;
49             }
50             m.clear();
51             int cnt=1;
52             for(int i=1;i<=n;i++)
53             {
54                 scanf("%s%s",ch1,ch2);
55                 if(!m[ch1]) m[ch1]=cnt++;
56                 if(!m[ch2]) m[ch2]=cnt++;
57                 connect(m[ch1],m[ch2]);
58             }
59         }
60     }
61     return 0;
62 }