网络交友plus
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
在网络社交的过程中，通过朋友，也能认识新的朋友。在某个朋友关系图中，假定 A 和 B 是朋友，B 和 C 是朋友，那么 A 和 C 也会成为朋友。即，我们规定朋友的朋友也是朋友。现在要求你每当有一对新的朋友认识的时候，你需要计算两人的朋友圈合并以后，朋友圈内名字字典序最小的那个人的名字。
输入格式
第一行：一个整数 $n(1 \leq n\leq 50000)$，表示有 $n$ 对朋友认识。接下来 $n$ 行：每行输入两个名字。表示新认识的两人的名字，用空格隔开。（名字是一个首字母大写后面全是小写字母且长度不超过 $20$ 的串）。
输出格式
对于每一对新认识的朋友，输出合并以后朋友圈内名字字典序最小的那个人的名字，每个输出占一行。样例
3
Fred Barney
Barney Aetty
Betty WilmaBarney
Aetty
Betty