Domino Tiles

Time limit1sMemory limit128 MB

Summary

Count pip frequencies to find the two odd endpoints of the domino chain, or report ambiguity when the chain can start anywhere.

Level: Medium5 of 10
Topics: Graph, Hash map
Solved: No attempts yet

Problem

Adrian builds a line out of domino tiles. Each tile is split into two fields, and each field shows a number of pips (dots). A tile may be rotated. Tiles are attached to either end of the line so that the two touching fields always show the same number of pips.

Adrian has $n$ tiles. Using all of them, a valid line can always be built. He wants to know the number of pips $p$ on the very first field of the finished line and the number of pips $k$ on the very last field.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10^6$ ), the number of domino tiles. Each of the next $n$ lines contains two integers $a_i$ , $b_i$ ( $1 \le a_i, b_i \le 10^9$ ), the number of pips on the left field and on the right field of the $i$ -th tile.

Output

Print the pip counts $p$ and $k$ at the two ends of the finished line on a single line: print $p$ then $k$ when $p < k$ , otherwise print $k$ then $p$ (that is, print the smaller value first). If the two end values are not uniquely determined, so the result is ambiguous, print the word 'NIE' instead.

Examples3

Example 1
Input
```
4
3 2
3 4
4 5
1 2
```
Expected output
```
1 5
```
Example 2
Input
```
1
5 5
```
Expected output
```
5 5
```
Example 3
Input
```
3
1 2
2 3
3 1
```
Expected output
```
NIE
```