Sprawdź triangulację

Limit czasu: 0.5s | Limit pamięci: 64MB

Dany jest zbiór przekątnych wielokąta prostego. Sprawdź czy jest to poprawna triangulacja.

Triangulacją nazwiemy pewien podział wielokąta na niezdegenerowane trójkąty, który spełnia poniższe warunki (wszystkie jednocześnie):

• każdy wierzchołek każdego trójkąta jest wierzchołkiem wielokąta,
• każdy bok wielokąta musi być bokiem dokładnie jednego trójkąta,
• pole części wspólnej każdych dwóch trójkątów wynosi zero,
• suma pól wszystkich trójkątów jest równa polu wielokąta,
• każdy trójkąt musi całkowicie zawierać się w wielokącie,
• każdy bok każdego trójkąta musi zawierać dokładnie dwa wierzchołki wielokąta.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ i $m$, oznaczające odpowiednio liczbę wierzchołków wielokąta oraz liczbę wybranych przekątnych.

Następne $n$ wierszy zawiera po dwie liczby całkowite $x_i, y_i$, oznaczające odciętą oraz rzędną $i$-tego wierzchołka wielokąta. Wierzchołki $i$ oraz $i+1$ sąsiadują ze sobą dla $i = 1, 2, ..., n-1$. Wierzchołki $n$ oraz $1$ także są ze sobą sąsiadują. Zagwarantowane jest, że podany wielokąt jest prosty.

Następne $m$ wierszy zawiera po dwie liczby całkowite $a_i$ oraz $b_i$, oznaczające że $i$-ta wybrana przekątna zaczyna się w $(x[a_i], y[a_i])$, a kończy w $(x[b_i], y[b_i])$ (w tym miejscu indeksujemy od zera).

Wyjście

Pierwszy wiersz wyjścia powinien zawierać OK, jeżeli podany zbiór przekątnych jest w pełni poprawną triangulacją lub WRONG w przeciwnym wypadku.

Ograniczenia

• $4 \le n \le 1\,000$
• $1 \le m \le 1\,000$
• $-10^9 \le x_i, y_i \le 10^9$
• $0 \le a_i, b_i < n$

Przykłady

Wejście 1

4 2
0 0
5 0
5 5
0 5
0 2
1 3

Wyjście 1

WRONG

Wyjaśnienie 1: Sytuację przedstawia rysunek:

Wejście 2

18 15
0 0
10 7
12 3
20 8
13 17
10 12
12 14
14 9
8 10
6 14
10 15
7 18
0 16
1 13
3 15
5 8
-2 9
5 5
1 3
1 15
1 17
3 7
3 15
4 6
4 7
7 15
8 15
9 11
9 14
9 15
11 14
12 14
15 17

Wyjście 2

OK

Wyjaśnienie 2: Sytuację przedstawia rysunek: