Background

The Flea Kingdom and the Cricket Kingdom are fighting fiercely.

The above is a tactical nuclear graphics card and is not related to the problem.

Problem Description

The territory of the Flea Kingdom can be viewed as a 2D Cartesian coordinate system.

The Flea Kingdom has $N+1$ cities. One city is the capital, located at $(0,0)$. The other $N$ cities are ordinary cities. Assume the capital is city $0$, and the other cities are numbered from $1$ to $N$. For each ordinary city $i$, it is located at $(x_i,y_i)$.

Due to limited financial resources, for each city $i$ that is not the capital, it will choose a city $j$ to build a bidirectional road. Let $dis(x,y)$ be the Euclidean distance between cities $x$ and $y$. Then for each city $i$ that is not the capital, the corresponding $j$ is the point that minimizes $dis(i,j)$ among all points satisfying $dis(j,0) \le dis(i,0)$ and $j \ne i$. If there are multiple valid $j$, choose the one with the smallest index.

Define the $\gamma$ value of a city as (the minimum number of roads needed to travel from this city to the capital) $+1$. If the capital cannot be reached, set the $\gamma$ value to $0$.

The Cricket Kingdom is going to carry out a tactical nuclear graphics card strike on the Flea Kingdom. This operation is divided into two groups: the Lorentz Group and the Ampere Group. Each group will strike some of the cities, and the two groups must strike each city in the Flea Kingdom exactly once.

For these two groups, fame is the most important, and the Cricket Kingdom’s evaluation standard is the sum of the $\gamma$ values of the cities struck in this operation. So you need to determine whether there exists a partition such that the sums of $\gamma$ values of the cities struck by the Lorentz Group and the Ampere Group are equal. If yes, output Yes, otherwise output No.

Input Format

The first line contains an integer $N$, representing the number of ordinary cities in the Flea Kingdom.

The next $N$ lines (lines $2$ to $N+1$): the $(i+1)$-th line contains two integers, representing the coordinates $(x_i,y_i)$ of city $i$.

Output Format

Output one string in a single line, Yes or No, indicating whether there exists a way to make the sums of $\gamma$ values of the cities struck by the Lorentz Group and the Ampere Group equal.

4
-1 -1
1 0
1 -2
-2 2

Yes

Hint

Sample Explanation

This figure looks like this:

For $C_1$: both $C_0$ and $C_2$ satisfy $dis(j,C_0) \le dis(C_1,C_0)$, but $C_0$ is closer to $C_1$, so add the edge $(C_1,C_0)$.

For $C_2$: only $C_0$ satisfies $dis(j,C_0) \le dis(C_2,C_0)$, so add the edge $(C_2,C_0)$.

For $C_3$: the three points $C_0$, $C_1$, and $C_2$ satisfy $dis(j,C_0) \le dis(C_3,C_0)$, but $C_2$ is closest to $C_3$, so add the edge $(C_3,C_2)$. Note that this is because when considering $C_3$, the optimal point is $C_2$, so $C_3$ builds a road to $C_2$, which is completely independent of the road $(C_2,C_0)$.

For $C_4$: all other points satisfy $dis(j,C_0) \le dis(C_4,C_0)$, but $C_0$ is closest to $C_4$, so add the edge $(C_4,C_0)$.

We obtain the following table:

So assign $C_0,C_1,C_2$ to the Lorentz Group, and assign $C_3,C_4$ to the Ampere Group.

Constraints

$1 \le N \le 500$, $-10^6 \le x_i,y_i \le 10^6$.

Special Note

Since the output of this problem is only Yes or No, this problem uses the minimum-score judging method, i.e., the minimum score among all test points is taken as the final result.

Translated by ChatGPT 5