网络交友plus 1837

Time Limit: 1 Sec Memory Limit: 128 MB

Submission：22 AC：5 Score：100

在网络社交的过程中，通过朋友，也能认识新的朋友。在某个朋友关系图中，假定 A 和 B 是朋友，B 和 C 是朋友，那么 A 和 C 也会成为朋友。即，我们规定朋友的朋友也是朋友。

现在要求你每当有一对新的朋友认识的时候，你需要计算两人的朋友圈合并以后，朋友圈内名字字典序最小的那个人的名字。

第一行：一个整数 $n(1 \leq n\leq 50000)$，表示有 $n$ 对朋友认识。

接下来 $n$ 行：每行输入两个名字。表示新认识的两人的名字，用空格隔开。（名字是一个首字母大写后面全是小写字母且长度不超过 $20$ 的串）。

对于每一对新认识的朋友，输出合并以后朋友圈内名字字典序最小的那个人的名字，每个输出占一行。

input:

3 Fred Barney Barney Aetty Betty Wilma

output:

Barney Aetty Betty