З'єднати точки

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

На площині задано \(n\) пар точок із цілими координатами. \(i\)-та пара містить точки \((x^{(i)}_1, y^{(i)}_1)\) та \((x^{(i)}_2, y^{(i)}_2)\). Усі \(2n\) точок є різними, і кожна з них лежить у квадраті \([0, n] \times [0, n]\).

Визначте, чи можна з’єднати кожну пару точок лінією (не обов’язково прямою) так, щоб виконувалися такі умови:

• кожна проведена лінія повністю лежить усередині квадрата \([0, n] \times [0, n]\) або на його межі;

• жодні дві лінії не перетинаються.

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість пар точок.

У кожному з наступних \(n\) рядків задано по чотири цілі числа \(x^{(i)}_1\), \(y^{(i)}_1\), \(x^{(i)}_2\) та \(y^{(i)}_2\) — координати двох точок \(i\)-ї пари.

Вихідні дані

Виведіть YES, якщо можна з’єднати всі пари точок без перетинів, або NO — інакше.

Обмеження

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

\(0 \le x^{(i)}_j, y^{(i)}_j \le n\) для всіх \(1 \le i \le n\), \(1 \le j \le 2\),

усі \(2n\) точок є різними.

Приклади

Вхідні дані (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

Примітки

У першому прикладі точки можна з’єднати так, як показано на рисунку вище.

У другому прикладі неможливо з’єднати точки так, щоб виконувалися умови задачі.

У третьому прикладі точки можна з’єднати так, як показано на рисунку вище.