Ostrich Passions
Johnny recently had a mishap with the ostrich named Chuck. After managing to gather all the escaped ostriches, the farmer contemplated how to prevent such chaos in the future.
Johnny decided to construct new housing for the birds. He established N watchtowers, each equipped with guards and spotlights, and connected them using electrified barbed wire fences. This setup encloses a yard in the shape of a polygon with N vertices, where the ostriches will reside. To facilitate easier monitoring, he plans to connect certain pairs of non-adjacent towers with walls that have machine gunners, thereby dividing the yard into N-2 triangular sections, creating enclosures for the ostriches. Importantly, these walls must lie entirely within the polygon, and each enclosure must be a non-degenerate triangle, meaning it must have a non-zero area.
The farmer now needs to determine how to divide the yard. Help him analyze all possible wall arrangements. Johnny is interested in two questions — one simpler and one more complex. First, he wants to know which pairs of towers can have a wall between them in any division plan. Second, he wants to know the total number of possible division plans.
Input
The first line of the input file contains the number N (3 ≤ N ≤ 300) — the number of towers.
The following N lines provide the descriptions of the towers in the order they are traversed. The i-th line contains two integers x_i, y_i, each not exceeding 10^4 in absolute value — the coordinates of the i-th tower.
It is guaranteed that the yard forms a polygon with a non-zero area that does not self-touch or self-intersect.
Output
In the first line, output K — the number of pairs of towers between which a wall can potentially be built.
Then, output K pairs of tower numbers, one per line. The numbers in each pair should be in ascending order, and the pairs should be sorted first by the first number, then by the second number.
The last line should contain a single number — the number of ways to divide the yard into enclosures. Since this number can be quite large, output it modulo 2^30 = 1073741824.