Divide Points
Contest: Good Bye 2019
Difficulty rating: 2300
Tags: constructive algorithms, geometry, math

You are given a set of $$$n\ge 2$$$ pairwise different points with integer coordinates. Your task is to partition these points into two nonempty groups $$$A$$$ and $$$B$$$, such that the following condition holds:

For every two points $$$P$$$ and $$$Q$$$, write the Euclidean distance between them on the blackboard: if they belong to the same group — with a yellow pen, and if they belong to different groups — with a blue pen. Then no yellow number is equal to any blue number.

It is guaranteed that such a partition exists for any possible input. If there exist multiple partitions, you are allowed to output any of them.

Input format:
The first line contains one integer $$$n$$$ $$$(2 \le n \le 10^3)$$$ — the number of points.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) — the coordinates of the $$$i$$$-th point.

It is guaranteed that all $$$n$$$ points are pairwise different.

Output format:
In the first line, output $$$a$$$ ($$$1 \le a \le n-1$$$) — the number of points in a group $$$A$$$.

In the second line, output $$$a$$$ integers — the indexes of points that you include into group $$$A$$$.

If there are multiple answers, print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, we set point $$$(0, 0)$$$ to group $$$A$$$ and points $$$(0, 1)$$$ and $$$(1, 0)$$$ to group $$$B$$$. In this way, we will have $$$1$$$ yellow number $$$\sqrt{2}$$$ and $$$2$$$ blue numbers $$$1$$$ on the blackboard.

In the second example, we set points $$$(0, 1)$$$ and $$$(0, -1)$$$ to group $$$A$$$ and points $$$(-1, 0)$$$ and $$$(1, 0)$$$ to group $$$B$$$. In this way, we will have $$$2$$$ yellow numbers $$$2$$$, $$$4$$$ blue numbers $$$\sqrt{2}$$$ on the blackboard.

Example input:
3
0 0
0 1
1 0

Example output:
1
1

Example input:
4
0 1
0 -1
1 0
-1 0

Example output:
2
1 2

Editorial:
Let's divide all points into $$$4$$$ groups by parity of their coordinates: $$$A_{00}$$$ — (even, even), $$$A_{01}$$$ — (even, odd), $$$A_{10}$$$ —(odd, even), $$$A_{11}$$$ — (odd, odd).
If all points belong to one group, for example, $$$A_{00}$$$, let's divide all coordinates by $$$2$$$ and start again. We just scaled down the image in $$$2$$$ times, and all distances between points also got smaller in exactly $$$2$$$ times, so any valid partition for new points remains valid for old points.
Note that this division by $$$2$$$ can't last long: as every division by $$$2$$$ decreases the distance between points in $$$2$$$ times, all the initial distances don't exceed $$$4\cdot 10^6$$$, and distances can't get smaller than $$$1$$$, we can't have more than $$$\log{4\cdot 10^6}$$$ such divisions.
From now on we suppose that at least two groups are nonempty.
If there is at least one point with the odd sum of coordinates, and at least one point with even sum of coordinates, we can put to $$$A$$$ all points with even sum of coordinates, and to $$$B$$$ — all with odd. Then for any two points $$$(x_1, y_1), (x_2, y_2)$$$, the square of distance between them $$$(x_1 - x_2)^2 + (y_1 - y_2)^2$$$ will be even if these points are from the same group, and odd if they are from different groups. As square of every yellow number will be even, and of every blue odd, no blue number will be equal to any yellow, and the partition would be valid.
If all points have even sum of coordinates, then only points $$$A_{00}$$$ and $$$A_{11}$$$ will be nonempty. Then we can set $$$A = A_{00}, B = A_{11}$$$: in this case for any two points $$$(x_1, y_1), (x_2, y_2)$$$, the square of distance between them $$$(x_1 - x_2)^2 + (y_1 - y_2)^2$$$ will be divisible by $$$4$$$, if these points are from the same group, and will give remainder $$$2$$$ under division by $$$4$$$, if from different.
Similarly, if all points have odd sum of coordinates, then only points $$$A_{01}$$$ and $$$A_{10}$$$ will be nonempty. Then we can set $$$A = A_{01}, B = A_{10}$$$: in this case for any two points $$$(x_1, y_1), (x_2, y_2)$$$, the square of distance between them $$$(x_1 - x_2)^2 + (y_1 - y_2)^2$$$ will be divisible by $$$4$$$, if these points are from the same group, and will give remainder $$$2$$$ under division by $$$4$$$, if from different.