{"problem":{"name":"D. Picture Day","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10219D"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\n\nOutput *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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10219D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}