{"raw_statement":[{"iden":"statement","content":"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.\n\nFor 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).\n\nFor 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.\n\nGiven the pairs of best friends, can you arrange them to make a perfect picture?\n\nThe first line of input contains a single *even* integer n (2 ≤ n ≤ 3 × 105), the number of students in the class.\n\nEach of the following n / 2 lines contains two integers ha hb (1 ≤ ha, hb ≤ 109), the heights of a pair of best friends in the class.\n\nOutput *any* valid arrangement of the class' heights such that each pair of best friends are standing next to each other.\n\nIf there is no answer, output *-1* on a single line.\n\n"},{"iden":"input","content":"The first line of input contains a single *even* integer n (2 ≤ n ≤ 3 × 105), the number of students in the class.Each of the following n / 2 lines contains two integers ha hb (1 ≤ ha, hb ≤ 109), the heights of a pair of best friends in the class."},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be an even integer, $ n \\geq 2 $.  \nLet $ P = \\{(h_{i,1}, h_{i,2}) \\mid i \\in \\{1, \\dots, n/2\\}\\} $ be a set of $ n/2 $ pairs of student heights.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 3 \\times 10^5 $  \n2. For each pair $ (h_{i,1}, h_{i,2}) \\in P $, $ 1 \\leq h_{i,1}, h_{i,2} \\leq 10^9 $  \n\n**Objective**  \nDetermine if there exists a sequence $ H = (h_1, h_2, \\dots, h_n) $ such that:  \n- Each pair $ (h_{i,1}, h_{i,2}) \\in P $ appears as two adjacent elements in $ H $, in either order $ (h_{i,1}, h_{i,2}) $ or $ (h_{i,2}, h_{i,1}) $.  \n- The sequence $ H $ is *unimodal*: there exists an index $ k \\in \\{1, \\dots, n\\} $ such that:  \n  $$\n  h_1 \\leq h_2 \\leq \\cdots \\leq h_k \\geq h_{k+1} \\geq \\cdots \\geq h_n\n  $$  \nIf such $ H $ exists, output any valid arrangement; otherwise, output $-1$.","simple_statement":"You have n students (n is even), grouped into n/2 pairs of best friends.  \nYou must line them up so that:  \n1. Each pair of friends stands next to each other (in any order).  \n2. The sequence of heights first stays non-decreasing, then non-increasing (like a hill).  \n\nGiven the pairs, output any valid arrangement of all heights, or -1 if impossible.","has_page_source":false}