Connect the Points

Обмеження: 2 сек., 512 МіБ

There are \(n\) pairs of points with integer coordinates on a two-dimensional plane. The \(i\)-th pair contains points \((x^{(i)}_1, y^{(i)}_1)\) and \((x^{(i)}_2, y^{(i)}_2)\). The \(2n\) points are distinct and each of them lies in the square \([0, n] \times [0, n]\).

Determine whether it is possible to connect every pair of points with a line (not necessarily a straight line) such that the following conditions hold.

• Every drawn line stays strictly inside or on the boundary of the square \([0, n] \times [0, n]\).

• No two lines intersect.

Вхідні дані

The first line contains an integer \(n\) – the number of pairs.

Each of the next \(n\) lines contains four integers \(x^{(i)}_1, y^{(i)}_1, x^{(i)}_2, y^{(i)}_2\) – the coordinates of the two points of the \(i\)-th pair.

Вихідні дані

Print YES, if it is possible to connect all pairs without intersections, or NO otherwise.

Обмеження

\(1 \le n \le 7\),

\(0 \le x^{(i)}_j, y^{(i)}_j \le n\) for all \(1 \le i \le n, 1 \le j \le 2\),

all \(2n\) points are distinct.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 0 0 3 0 1 1 2 2 0 2 1 2	YES

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 0 1 2 1 1 0 1 2	NO

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 0 0 2 2 2 0 1 1	YES

Примітки

In the first sample, it is possible to connect the points as shown in the picture above.

In the second sample, it is impossible to connect the points such that the conditions are satisfied.

In the third sample, it is possible to connect the points as shown in the picture above.