{"problem":{"name":"I. Interplanetary","description":{"content":"The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10234I"},"statements":[{"statement_type":"Markdown","content":"The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, p, M, m \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ C = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of complaints, where $ 1 \\le x_i < y_i \\le p $.  \nLet $ S = \\{(l_j, r_j) \\mid j \\in \\{1, \\dots, p\\}\\} $ be the set of power constraints for each station $ j $, where $ 1 \\le l_j \\le r_j \\le M $.  \nLet $ I = \\{(u_k, v_k) \\mid k \\in \\{1, \\dots, m\\}\\} $ be the set of interfering station pairs, where $ 1 \\le u_k < v_k \\le p $.\n\n**Constraints**  \n1. For each complaint $ (x, y) \\in C $, at least one of stations $ x $ or $ y $ must be selected.  \n2. For each selected station $ j $, the chosen signal power $ f $ must satisfy $ l_j \\le f \\le r_j $.  \n3. For each interfering pair $ (u, v) \\in I $, stations $ u $ and $ v $ cannot both be selected.  \n4. The signal power $ f $ must be an integer in $ [1, M] $.\n\n**Objective**  \nFind an integer $ f \\in [1, M] $ and a subset $ T \\subseteq \\{1, \\dots, p\\} $ such that:  \n- $ \\forall (x, y) \\in C $, $ x \\in T $ or $ y \\in T $,  \n- $ \\forall j \\in T $, $ l_j \\le f \\le r_j $,  \n- $ \\forall (u, v) \\in I $, $ \\neg (u \\in T \\land v \\in T) $.  \n\nIf such $ f $ and $ T $ exist, output $ |T| $, $ f $, and the elements of $ T $. Otherwise, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10234I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}