Problem Description

You are playing a prank with your friend, who starts at the position $(0,0)$. Each cell has a color, and there are $N$ portals. When your friend enters a portal, they will be randomly teleported to one of the $N$ portals with equal probability (including possibly the same portal, and if there is a portal at $(0,0)$, they will also be teleported).

Unfortunately, your friend is unaware of the existence of the portals and will only determine their current cell and its color based on the cells they move through. You need to ensure that no matter how they move, the color of the cell they see always matches the color they believe they are in.

You can color the cells freely, but please maximize the number of colors used. It is clear that coloring everything with one color is always the minimal solution.

Input Format

The first line contains an integer $N$, representing the number of portals.

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

Output Format

Output a single number representing the maximum number of colors you can use. If an infinite number of colors can be used, output $-1$.

Sample Input and Output

Sample Input #1

3
1 1
1 3
3 2

Sample Output #1

4

Sample Input #2

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

Sample Output #2

1

Sample Input #3

1
1 -1

Sample Output #3

-1

Notes

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

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

After the sequence of moves, your friend will think they have returned to the starting cell $(0,0)$, but they might actually end up at $(0,2)$ or $(2,1)$. They have already seen the color of the cell $(0,0)$ at the start, so if they now see a different color, they will realize that there must be portals. 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 can make your friend think they end up at cell $(0,0)$ while they are actually at $(1,0)$, so these cells can safely use different colors.

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

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

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

见题面 Input 部分

见题面 Output 部分