题目描述

俗话说：朋友的朋友也是朋友！

在社交的过程中，通过朋友，也能认识新的朋友。比如X和Y是朋友，Y和Z是朋友，那么X和Z也会成为朋友。

每当有一对新的朋友认识的时候，请计算两人所在朋友圈的总人数。

输入格式

第一行有一个整数$n$，表示有$n$对新认识的朋友。

第$2$~$n+1$行，每行输入两个字符串，用空格隔开，表示两个人的姓名。

输出格式

每增加一对朋友关系，输出两人所在朋友圈的总人数。

样例

3
Xiaoda Xiaoke
Xiaoke Xiaomei
John Jack

2
3
2

提示

样例解释

朋友圈有两个人，分别是Xiaoda、Xiaoke；

朋友圈有三个人，分别是Xiaoda、Xiaoke、Xiaomei；

朋友圈有两个人，分别是John、Jack。

数据范围

对于$100\%$的数据：$1<=n<=5*10^4$，人名只包含字母且长度不超过50。