~N~ mobs in his farm, each with a type from ~1~ to ~M~. There is at least one mob of each type. He wants to become more organized, so he wants to build a pen for one of his mobs. Specifically, he wants his pen to enclose all the mobs of some type ~C~, yet not enclose any mobs not of type ~C~. He also wants to be able to walk in a straight line from his base to his mine without having to go through more than ~2~ fence gates. However, you do not know where his base or his mine are (that is a secret), so you want to build the enclosure such that no matter where his base and his mine are, he can walk from his base to his mine without crossing the enclosure boundary more than twice. Can you help him determine if this is possible? As the farm is gigantic, you can assume the plane is continuous (i.e. there is an arbitrarily large number of blocks in ~[x,x+\epsilon) \times [y,y+\epsilon)~ for ~\epsilon>0~).is playing minecraft! He has
The first line will contain two integers ~N\ (1 \leq N \leq 2\cdot 10^3), M\ (1 \leq M \leq N)~, the number of mobs, and the number of different types of mobs.
The next ~N~ lines will contain ~3~ integers ~x_i,y_i\ (-10^9 \leq x_i,y_i \leq 10^9), c_i\ (1 \leq c_i \leq M)~, the position and type of each mob.
YES if some mob can be enclosed, or
Subtask 1 (50%)
~N \leq 500~
Subtask 2 (50%)
No further constraints.
6 2 0 0 1 2 2 1 2 0 1 1 1 2 2 3 2 3 1 2