Portal

You want to prank your best friend by placing them on cell $(0, 0)$ of an infinite grid of coloured cells. The friend then moves one step at a time to one of the four adjacent cells, forever.

$N$ cells of the grid contain a portal. When the friend steps on a portal, they instantly teleport to a random portal, which may be the same one they just stepped on. If there is a portal at $(0, 0)$, the friend is teleported at the start as well.

You want the friend to never notice the portals. The friend only sees the colour of the cell they are on, so the colours seen must never change from the friend's point of view. If the friend thinks they have entered a cell again (for example by moving left and then right), they must see the same colour as the first time.

When the friend steps on a portal, they see the colour of the cell they step on and the colour of the cell they are teleported to. So all portal cells must have the same colour.

Colour the grid with as many colours as possible. Colouring every cell the same colour works, but you want more colours than that.

For example, with portals at $(1, 1)$, $(1, 3)$ and $(3, 2)$, the friend moves up, right, down, left. The friend ends up back at $(0, 0)$ in their own view, but may actually be at $(0, 2)$ or $(2, 1)$. These three cells must share a colour, while $(0, 0)$ and $(1, 0)$ may differ.

Print the maximum number of colours that can be used without the friend noticing the portals, or $-1$ if the number of colours is unlimited.

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

The next $N$ lines each contain two integers $x_i$ and $y_i$, meaning there is a portal at cell $(x_i, y_i)$.

Print a single integer, the maximum number of colours that can be used, or $-1$ if the number of colours is unlimited.

$1 \le N \le 10^5$

$-10^6 \le x_i, y_i \le 10^6$ for all $1 \le i \le N$

No two portals share the same coordinates.