C$.$ Rectangle Merging

time limit per test: $1$ second

memory limit per test: $256$ megabytes

input: standard input

output: standard output

You are given a rectangles. In the first second, only the first rectangle of size ax by is considered. Then, on the i$-$th second, a rectangle of size ax by is attached to one of the sides of the current rectangle without overlapping, so that their union remains a rectangle.

For this, the current rectangle and the rectangle of size a$,$ x by must be attached to each other by an equal side. The rectangle could be rotated by $90\%$ and attached to any side of the current rectangle if it had an equal side to it

Based on the information about the sizes of all a rectangles, determine if they can all be merged in such order, and if yes, what possible rectangles could result in the end.

Input

The first line of input contains a single number the number of rectangles $(1$ n $105)$

In the i$-$th of the following lines, two integers a$,$ and by are given, separated by a space the sizes of the i$-$th rectangle $(1$ a$,$ b $<1012).$ Note that the sizes of the rectangles may not fit into a $32-$bit Integer type int

Output

In the first line, output a single integer k the number of possible size variations of the final rectangle. If it is not possible