{"raw_statement":[{"iden":"statement","content":"The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf\n\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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 $.","simple_statement":"You are given n complaints, p radio stations, max power M, and m interfering pairs.\n\nEach complaint says: at least one of two stations (x_i, y_i) must cover the whole city.\n\nEach station i can only be used if signal power f is in [l_i, r_i].\n\nSome station pairs (u_i, v_i) cannot both be chosen — they interfere.\n\nChoose a signal power f (1 ≤ f ≤ M) and a set of stations such that:\n\n- For every complaint (x_i, y_i), at least one of x_i or y_i is chosen.\n- No two chosen stations interfere.\n- f is in [l_i, r_i] for every chosen station i.\n\nOutput: number of chosen stations k, power f, and the list of station indices.\n\nIf impossible, output -1.","has_page_source":false}