Absurdistan 的居民直到去年才发现如何修建道路。发现这一技术后，每个城市都决定修建一条属于自己的道路，将该城市连接到另一个城市。每条新建的道路都可以双向通行。

Photo by Ivan McClellan

你买了一本旅游指南，上面有该国新建道路的地图。然而，由于你对历史非常感兴趣，你想知道到底是哪个城市修建了哪条道路。

给定 $n$ 条道路的描述，你能否为 $n$ 个城市分配道路，使得每个城市恰好修建了一条道路？如果存在多种分配方案，任何一种方案都可以。题目保证至少存在一个解。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示城市和道路的数量。接下来 $n$ 行，每行包含两个整数。一行中的 “$a\ b$” 表示城市 $a$ 和 $b$ 之间有一条道路，$1 \le a, b \le n, a \neq b$。同一对城市之间可能存在多条道路。

输出格式

输出 $n$ 行，每行包含两个整数 “$a\ b$”，表示城市 $a$ 和 $b$ 之间的道路是由城市 $a$ 修建的。输入中的每条道路必须在输出中恰好出现一次。如果存在多种解，你可以输出其中任意一种，且道路的输出顺序不限。

样例

输入格式 1

4
1 2
2 3
3 1
4 1

输出格式 1

4 1
2 1
3 2
1 3

输入格式 2

2
1 2
1 2

输出格式 2

2 1
1 2