405953: GYM102191 D Picture Day

You have a class of even number of students n. The class can be divided into n / 2 pairs of best friends, who always like to stay next to each other. Unfortunately, this makes your job harder because today is picture day.

For a perfect picture, you want to align the students in order of non-decreasing heights then non-increasing heights. Each pair of best friends must be next to each other, however, their relative order does not matter (friends a and b ordered as ab or ba both work).

For example, [1, 2, 4, 3, 3, 1] ,[1, 5, 10, 11], [11, 10, 5, 5], [3, 3, 3, 3] are perfect height arrangements as numbers first do not decrease, then they do not increase.

Given the pairs of best friends, can you arrange them to make a perfect picture?

The first line of input contains a single even integer n (2 ≤ n ≤ 3 × 10⁵), the number of students in the class.

Each of the following n / 2 lines contains two integers h_a h_b (1 ≤ h_a, h_b ≤ 10⁹), the heights of a pair of best friends in the class.

Output any valid arrangement of the class' heights such that each pair of best friends are standing next to each other.

If there is no answer, output -1 on a single line.

8
1 3	
4 2
6 7 
5 7	

2 4 5 7 7 6 3 1