#C11378. Non-intersecting Cycle Formation

    ID: 40687 Type: Default 1000ms 256MiB

Non-intersecting Cycle Formation

Non-intersecting Cycle Formation

You are given n points in the plane, each with integer coordinates. Your task is to determine whether it is possible to connect these points with line segments to form a single cycle such that:

  • Every point is connected to exactly two other points.
  • No two line segments intersect except at the endpoints.

A key observation is that such a formation exists if and only if n is even, i.e., $$n \mod 2 = 0$$.

For example, if there are 4 points, it is possible to form a cycle, whereas with 5 points it is impossible.

inputFormat

The input is given via standard input (stdin) and has the following format:

n
x1 y1
x2 y2
...
xn yn

Where n is the number of points, and each of the next n lines contains two integers representing the coordinates of a point.

outputFormat

Output a single line to standard output (stdout):

POSSIBLE

If a non-intersecting cycle formation is possible, or

IMPOSSIBLE

if it is not possible.

## sample
4
0 0
2 2
2 0
0 2
POSSIBLE

</p>