Background

Translated from BalticOI 2024 Day1 T2.

Problem Description

You are playing a prank on your friend. Your friend starts at position $(0,0)$. Each grid cell has a color. There are $N$ portals. When your friend enters a portal cell, they will be teleported uniformly at random to one of the $N$ portals (possibly the same portal; if there is a portal at $(0,0)$, they must also be teleported).

Unfortunately, your friend does not know that portals exist. They can only determine their current cell and its color based on the path they have walked. You need to ensure that no matter how they move, the color of the cell they see is always the same as the color of the cell they believe they are in.

You may color the grid arbitrarily, but you must maximize the number of colors used. It is not hard to see that coloring everything with one color is always the smallest solution.

Input Format

The first line contains an integer $N$, meaning there are $N$ portals.

The next $N$ lines each contain two integers $(x_i,y_i)$, representing the coordinates of a portal.

Output Format

Output one number, the maximum number of colors you can use. If you can use infinitely many colors, output $-1$.

3
1 1
1 3
3 2

4

5
0 0
1 0
-1 0
0 1
0 -1

1

1
1 -1 

-1

Hint

For all testdata, $1 \leq N \leq 10^5$, $-10^6 \leq x_i,y_i \leq 10^6$, and all $(x_i,y_i)$ are pairwise distinct.

For Sample 1, the portals are placed at $(1,1)$, $(1,3)$, and $(3,2)$. If your friend moves in the following order: up, right, down, left.

After this sequence of moves ends, your friend will believe they have returned to the starting cell $(0,0)$, but in reality they may also end up at $(0,2)$ or $(2,1)$. They have already seen the color of cell $(0,0)$ at the start, so if they now see a different color, they will realize that portals must exist. We do not want this to happen, so we must choose the same color for these three cells.

There is no sequence of moves that makes your friend believe they finally end up in cell $(0,0)$ while actually ending up in $(1,0)$, so these cells can safely use different colors.

You can see a coloring scheme using $4$ colors in the example below. For this example, it is impossible to use more than $4$ colors.

For Sample 2, let us consider a different example, where there are portals at cells $(0,0)$, $(0,1)$, $(1,0)$, $(0,-1)$, and $(-1,0)$. Suppose your friend tries to reach cell $(1,3)$ by first moving right once and then moving up three times. One possibility is that if they are teleported there at the start and after every step, then they will finally reach cell $(0,0)$. If your friend now returns to what they believe is cell $(0,0)$ by moving down three times and then left once, and during this process they are not teleported away from their current cell, then they will finally arrive at $(-1,-3)$. Your friend will believe for the second time that they are at cell $(0, 0)$, and expect to see the same color. So you need to color $(-1,-3)$ and $(0, 0)$ with the same color.

Note that there is nothing special about choosing cell $(1,3)$ as the starting point. You can also prove that other cells must share the same color as $(0,0)$.

Translated by ChatGPT 5