Two Dots

"Only 1% can solve this problem!!!"

어느 날 Yunee는 "Two Dots"라는 게임의 광고를 보았다. 이 게임의 목표는 같은 색의 점들을 모두 쌍으로 이어 주는 것이다.

규칙은 다음과 같다. 게임 영역은 한 변의 길이가 $L\times L$인 정사각형이다. 정사각형 위에 $N$개의 점이 있는데, 일부는 내부에, 나머지는 경계 위에 있다. 점들은 색에 따라 $N/2$개의 쌍으로 나뉜다. 곡선을 그려 한 쌍의 점을 이을 수 있다. 선은 정사각형 내부에 완전히 놓여야 하며, 서로 교차해서는 안 된다.

Yunee는 광고에 실린 문제가 절대 풀리지 않는다는 것을 알아냈다. Yunee는 이에 화가 나서, 문제를 풀 수 없다는 것을 증명하여 이 광고를 허위 광고로 신고하려고 한다. 문제를 풀 수 없다면 이 문제를 풀 수 있는 사람은 0%뿐이다!!!

주어진 문제를 풀 수 있는지 판별하는 프로그램을 작성하라.

첫 줄에 정수 $L$ $(1\leq L \leq 100{,}000)$과 짝수 $N$ $(2\leq N\leq \min\{300{,}000, (L+1)^2\})$이 주어진다. $L$은 게임 영역의 한 변 길이이고, $N$은 점의 개수이다. 게임 영역의 네 꼭짓점은 $(0, 0)$, $(L, 0)$, $(L, L)$, $(0, L)$이다.

이어지는 $N$개의 줄은 점을 나타낸다. $i$번째 줄에는 $i$번째 점의 좌표 $x, y$와 색 $c$가 주어진다 $(0 \leq x, y \leq L, 1 \leq c \leq N/2)$. $N$개 점의 좌표는 모두 다르다. 각 색 $c=1,\cdots,N/2$에 대해 정확히 두 점이 있다.

문제를 풀 수 있으면 1%를, 그렇지 않으면 0%를 출력한다.