{"problem":{"name":"I. The Secret","description":{"content":"The random integer y is either zero or one, and the random integer x is between 1 and N. The value y is a secret. We are given an interval , and we need  to hold at all times in order to guarantee the","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10159I"},"statements":[{"statement_type":"Markdown","content":"The random integer y is either zero or one, and the random integer x is between 1 and N. The value y is a secret. We are given an interval , and we need  to hold at all times in order to guarantee the confidentiality of the secret. (I.e. we want that .)\n\nThe values  and  are known for all i between 1 and N. Unfortunately, the dependency between x and y means that someone who learns x might be able to compute good bounds on . Fortunately, the value of x is not yet known. Your goal is to censor the value of x such that nobody can learn too much about the value of y.\n\nTo censor x means to partition the set {1, 2, ..., N} into equivalence classes A1, ..., AM such that, as soon as x is determined, only the index i of the unique equivalence class Ai that contains x becomes known (instead of the precise value of x).\n\nYou therefore have to find a partition  such that for all i between 1 and M, the confidentiality of the secret is maintained, i.e. .\n\n(Hint: Recall that , where  means that both A and B are true, and .)\n\nIn case there are multiple solutions, compute an arbitrary solution that maximizes the number of equivalence classes that contain only a single element.\n\nThe first line of the input contains two space-separated integers A and B such that a·106 = A and b·106 = B. The second line of the input contains the single integer N (1 ≤ N ≤ 106).\n\nThe i-th of the next N lines of the input contains integers Xi and Yi such that  and .\n\nIf there is no solution, print the single integer  - 1.\n\nOtherwise, the first line of the output should contain the size M of the partition. The i-th of the following M lines should contain an integer Ki, the number of elements of the i-th equivalence class Ai, followed by Ki numbers, the elements of Ai.\n\nYou may print the equivalence classes and their elements in any order.\n\n## Input\n\nThe first line of the input contains two space-separated integers A and B such that a·106 = A and b·106 = B. The second line of the input contains the single integer N (1 ≤ N ≤ 106).The i-th of the next N lines of the input contains integers Xi and Yi such that  and .\n\n## Output\n\nIf there is no solution, print the single integer  - 1.Otherwise, the first line of the output should contain the size M of the partition. The i-th of the following M lines should contain an integer Ki, the number of elements of the i-th equivalence class Ai, followed by Ki numbers, the elements of Ai.You may print the equivalence classes and their elements in any order.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ A, B \\in \\mathbb{Z} $ with $ A = a \\cdot 10^6 $, $ B = b \\cdot 10^6 $.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let $ (x_i, y_i) \\in \\mathbb{Z}^2 $ be given, where $ x_i \\in [1, N] $, $ y_i \\in \\{0, 1\\} $.  \nLet $ Y = \\{ y_i \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of secret values.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^6 $  \n2. $ y_i \\in \\{0, 1\\} $ for all $ i \\in \\{1, \\dots, N\\} $  \n3. For any equivalence class $ A_j $ in the partition, if $ \\exists i, k \\in A_j $ such that $ y_i \\ne y_k $, then the partition is invalid.  \n   That is: $ \\forall j \\in \\{1, \\dots, M\\}, \\; \\forall i, k \\in A_j, \\; y_i = y_k $  \n\n**Objective**  \nFind a partition $ \\{A_1, \\dots, A_M\\} $ of $ \\{1, 2, \\dots, N\\} $ such that:  \n- For each $ A_j $, all elements $ i \\in A_j $ have identical $ y_i $.  \n- Maximize the number of singleton classes (i.e., classes with $ |A_j| = 1 $).  \n\nIf no such partition exists (i.e., if two indices $ i, k $ with $ x_i = x_k $ but $ y_i \\ne y_k $ exist), output $-1$.  \n\nOtherwise, output:  \n- First line: $ M $  \n- Next $ M $ lines: for each class $ A_j $, output $ |A_j| $ followed by the elements of $ A_j $ (in any order).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10159I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}