{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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 ."},{"iden":"output","content":"If 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."},{"iden":"examples","content":"Input450000 5500006100000 449999100000 550001100000 400000100000 600000300000 500000300000 500000Output42 1 22 3 41 51 6Input500000 5000005200000 500000200000 500000200000 500000200000 500000200000 500000Output51 11 21 31 41 5Input228503 52083911000000 379204Output11 1"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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).","simple_statement":"We are given N pairs (X_i, Y_i).  \nWe need to group the indices 1 to N into classes so that:  \nFor each class, all pairs (X_i, Y_i) in it must have the same Y_i.  \nBecause if two indices in the same class have different Y_i, then knowing which class X is in might reveal info about Y — which we must avoid.  \n\nSo:  \n- Group indices by their Y_i value.  \n- Each group is an equivalence class.  \n- All indices with the same Y_i go together.  \n- If two indices have different Y_i, they must be in different classes.  \n\nThis is the only way to guarantee that knowing the class tells you nothing about Y — because within a class, Y is fixed.  \n\nWe want to maximize the number of singleton classes.  \nThat means: if a Y_i appears only once, put it in its own class.  \nIf a Y_i appears multiple times, put all those indices in one class.  \n\nSo:  \n- Group indices by Y_i.  \n- Each unique Y_i → one class containing all indices with that Y_i.  \n- Output: number of classes, then each class (size + list of indices).  \n\nIf any class has conflicting constraints? None — the only constraint is Y must be constant per class.  \n\nSo algorithm:  \n1. Read A, B (but we don’t use them — ignore).  \n2. Read N.  \n3. For i from 1 to N: read X_i, Y_i.  \n4. Group indices (1-indexed) by Y_i.  \n5. Each group is a class.  \n6. Output number of groups.  \n7. For each group, output size and the list of indices in that group.  \n\nNote: We don’t care about X_i at all. Only Y_i matters for grouping.  \n\nExample:  \nInput:  \nA B  \nN  \n1 2  \n2 2  \n3 3  \n\nGroups:  \nY=2 → [1,2]  \nY=3 → [3]  \n\nOutput:  \n2  \n2 1 2  \n1 3  \n\nThat’s it.  \n\nNo solution? Only if N=0? But N≥1. So always solvable.  \n\nSo we never output -1.  \n\nFinal simplified statement:  \n\nGroup the indices 1 to N by their Y value. Each group is a class. Output the groups.","has_page_source":false}