{"problem":{"name":"I. Data Structures Exam (B)","description":{"content":"As predicted, a number of students were able to cheat during the last exam, and Doctor Sufyan wanted to avoid that in the future. He wanted to come up with a specific seating order beforehand that gua","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10140I"},"statements":[{"statement_type":"Markdown","content":"As predicted, a number of students were able to cheat during the last exam, and Doctor Sufyan wanted to avoid that in the future. He wanted to come up with a specific seating order beforehand that guarantees that no two friends will be able to cheat from each other, in case he had to use the meeting room again.\n\nGiven the number of students in his class N, which is equal to the number of seats around the table, and the pairs of friends that are likely to cheat from one another, determine whether or not it's possible to find a seating order that guarantees that no cheating incidents will occur.\n\nThe first line of input contains two space-separated integers N, M (3 ≤ N ≤ 104) , the number of students (and seats) and the number of cheating pairs of friends, respectively.\n\nEach of the following M lines contains two space-separated integers a b (1 ≤ a, b ≤ N) (a ≠ b), represent a pair of friends that are most likely to cheat.\n\nIt is guaranteed that each pair of students will appear at most once.\n\nIf it is impossible to find a seating order that guarantees that no cheating incidents will occur, print -1. Otherwise, print N distinct integers, on a single line, representing the seating order of the students around the table.\n\n## Input\n\nThe first line of input contains two space-separated integers N, M (3 ≤ N ≤ 104) , the number of students (and seats) and the number of cheating pairs of friends, respectively.Each of the following M lines contains two space-separated integers a b (1 ≤ a, b ≤ N) (a ≠ b), represent a pair of friends that are most likely to cheat.It is guaranteed that each pair of students will appear at most once.\n\n## Output\n\nIf it is impossible to find a seating order that guarantees that no cheating incidents will occur, print -1. Otherwise, print N distinct integers, on a single line, representing the seating order of the students around the table.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of students and seats.  \nLet $ M \\in \\mathbb{Z} $ be the number of forbidden adjacent pairs (friendships that may lead to cheating).  \nLet $ G = (V, E) $ be an undirected graph where:  \n- $ V = \\{1, 2, \\dots, N\\} $ is the set of students (vertices),  \n- $ E \\subseteq \\binom{V}{2} $ is the set of edges representing cheating pairs (each $ \\{a, b\\} \\in E $ means students $ a $ and $ b $ are friends and must not be seated adjacently).  \n\n**Constraints**  \n1. $ 3 \\leq N \\leq 10^4 $  \n2. $ 0 \\leq M \\leq \\binom{N}{2} $  \n3. Each edge in $ E $ is unique and undirected: $ \\{a, b\\} \\in E \\Rightarrow a \\ne b $  \n4. The seating is a cyclic permutation $ \\pi \\in S_N $, i.e., a circular arrangement of all $ N $ students.  \n\n**Objective**  \nDetermine whether there exists a cyclic ordering $ \\pi = (\\pi_1, \\pi_2, \\dots, \\pi_N) $ such that for all $ i \\in \\{1, \\dots, N\\} $:  \n$$\n\\{\\pi_i, \\pi_{i+1}\\} \\notin E \\quad \\text{(with } \\pi_{N+1} = \\pi_1\\text{)}\n$$  \nIf such an ordering exists, output any valid $ \\pi $. Otherwise, output $-1$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10140I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}