Description

同OJ3522 数据范围：n<=100000

Format

Input

Output

Samples

7
1 2
5 7
2 5
2 3
5 6
4 5

5