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

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

2 секунди
512 мегабайтів
Складна

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

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

Вхідні дані

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

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

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,

усі точок є різними.

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

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

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

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