{"problem":{"name":"C. Самый сложный предмет","description":{"content":"Однажды Макс, едва пережив очередной тяжёлый экзамен, задался вопросом — какая из дисциплин, преподаваемых в университете, является наиболее сложной? Листая учебный план, Макс выяснил, что для изучен","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10126C"},"statements":[{"statement_type":"Markdown","content":"Однажды Макс, едва пережив очередной тяжёлый экзамен, задался вопросом — какая из дисциплин, преподаваемых в университете, является наиболее сложной?\n\nЛистая учебный план, Макс выяснил, что для изучения некоторых предметов необходимо предварительно освоить другие предметы. Так, например, чтобы изучать «Технологии программирования», нужно сдать «Основы программирования», перед «Цифровой схемотехникой» следует пройти «Электротехнику и электронику», а для «Высокопроизводительных вычислений» требуются «Алгоритмы и структуры данных» и «Машинно-ориентированное программирование».\n\nМакс предположил, что чем больше у предмета список предварительных требований, тем сложнее этот предмет. Более формально, сложность 0 имеют предметы без предварительных требований, сложность 1 — предметы, основывающиеся хотя бы на одном предмете сложности 0, сложность 2 — предметы, основывающиеся хотя бы на одном предмете сложности 1, и так далее.\n\nМакс уже составил список предварительных требований для всех изучаемых предметов. Помогите ему определить предмет, сложность которого является максимальной.\n\nПервая строка содержит целое число N (1 ≤ N ≤ 104) — количество учебных предметов.\n\nВторая строка содержит N различных слов Si (1 ≤ |Si| ≤ 20), состоящих из строчных латинских букв и знаков подчёркивания, — названия каждого из предметов.\n\nТретья строка содержит целое число M (0 ≤ M ≤ 105) — количество требований.\n\nСледующие M строк описывают предварительные требования. Каждая из них содержит слова Aj и Bj и () — соответственно название предмета, который изучается ранее, и название предмета, который изучается позднее.\n\nВыведите названия всех предметов, имеющих максимальную сложность, в алфавитном порядке.\n\nЕсли сложность хотя бы одного из предметов не может быть определена, выведите Impossible.\n\n## Входные Данные\n\nПервая строка содержит целое число N (1 ≤ N ≤ 104) — количество учебных предметов.Вторая строка содержит N различных слов Si (1 ≤ |Si| ≤ 20), состоящих из строчных латинских букв и знаков подчёркивания, — названия каждого из предметов.Третья строка содержит целое число M (0 ≤ M ≤ 105) — количество требований.Следующие M строк описывают предварительные требования. Каждая из них содержит слова Aj и Bj и () — соответственно название предмета, который изучается ранее, и название предмета, который изучается позднее.\n\n## Выходные Данные\n\nВыведите названия всех предметов, имеющих максимальную сложность, в алфавитном порядке.Если сложность хотя бы одного из предметов не может быть определена, выведите Impossible.\n\n## Примеры\n\nВходные данные6algorithms discrete_math higher_math history prog_basics prog_technologies4discrete_math algorithmsprog_basics prog_technologiesprog_basics algorithmshigher_math discrete_mathВыходные данныеalgorithmsВходные данные4physics machine_learning electronics ai_systems2physics electronicsmachine_learning ai_systemsВыходные данныеai_systems electronics\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Let $ n, m \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 2000 $, $ 1 \\leq m \\leq 2000 $.  \nLet $ E = \\{ (c_{1,i}, c_{2,i}) \\mid i \\in \\{1, \\dots, m\\} \\} $ be the set of daily contract pairs, where $ c_{1,i}, c_{2,i} \\in \\{1, \\dots, n\\} $, $ c_{1,i} \\ne c_{2,i} $.  \n\nLet $ d_j \\in \\mathbb{Z}_{\\geq 0} $ denote the total number of small contracts signed with company $ j \\in \\{1, \\dots, n\\} $ over the $ m $ days.  \n\nDefine $ k \\in \\mathbb{Z}^+ $ as the number of small contracts into which each of the $ n $ large contracts was split.  \n\n**Constraints:**  \n1. For each $ j \\in \\{1, \\dots, n\\} $, $ d_j \\leq k $ (since each company originally had one large contract, split into $ k $ small ones).  \n2. For each day $ i \\in \\{1, \\dots, m\\} $, the pair $ (c_{1,i}, c_{2,i}) $ is valid (distinct companies).  \n3. The assignment of small contracts must allow for the possibility of continuing to sign exactly two contracts per day (possibly beyond day $ m $), without exceeding the limit of $ k $ contracts per company.  \n\n**Objective:**  \nFind the minimal $ k \\in \\mathbb{Z}^+ $ such that:  \n- $ d_j \\leq k $ for all $ j \\in \\{1, \\dots, n\\} $,  \n- and the multigraph $ G = (V, E) $ with $ V = \\{1, \\dots, n\\} $ and edge multiset $ E $ (each edge corresponds to a day’s pair) can be extended to a $ k $-regular multigraph (i.e., every vertex has degree $ k $) by adding edges.  \n\nThat is, find the minimal $ k \\geq \\max_{j} d_j $ such that $ \\sum_{j=1}^n d_j $ is even and $ k \\cdot n - \\sum_{j=1}^n d_j $ is even and non-negative, and the graph can be completed to a $ k $-regular multigraph (which is always possible if the degree sequence is graphical and satisfies the above parity and bound conditions).  \n\nSince we only require existence of a completion, the necessary and sufficient condition is:  \n$$\nk \\geq \\max_{1 \\leq j \\leq n} d_j \\quad \\text{and} \\quad k \\cdot n \\equiv \\sum_{j=1}^n d_j \\pmod{2}\n$$\n\nThus, the minimal such $ k $ is:  \n$$\nk = \\min \\left\\{ t \\in \\mathbb{Z}^+ \\,\\middle|\\, t \\geq \\max_j d_j \\text{ and } t \\cdot n \\equiv \\sum_j d_j \\pmod{2} \\right\\}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10126C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}