Gridsylvania is a small country with a crazy royal family. Each generation passes new decrees that make very little sense. Once, around 100 years ago, King Mesh the Magnificent decided that all cities must have their streets laid out in a regular grid. The work on his project has been plagued with scandal, such as the Great Grid Graft, but is now complete, giving Gridonia some of the most convoluted architecture in the world.King Ned the Repairman has noticed the general state of disrepair in some of the older construction. He has taken a personal interest in micromanaging the repairs, moving repair teams from intersection to intersection fixing everything from pot holes to fallen bridges.
The oldest city, Latticia, is home to a yearly conference for geometricians from around the globe. This is obviously a big event for such a small country. Being the oldest city, Latticia is also the center of the most repair work.
The geometricians who come to Latticia play an odd game. They walk for a block, turn at a right angle, walk for two blocks, turn again, and continue until they either return to their starting point or know they cannot. There is great prestige in being the geometrician who is the most unerring walker of golygons, as these figures are called.
The current repairs make this job a little more difficult. No golygon walker will dare cross an intersection where the King may be working. The King can draft any passer-by into any repair project. This would be very bad for the geometricians, who would doubtless crumble under the physical strain of real work.
A little travel agency (well, it can hardly be a big one under such circumstances) has decided to capitalize on the golygon competitions. They want to make maps showing every possible golygon and sell these to the geometricians.
The travel agency desperately wants to publish maps showing all the possible golygons, but the King moves the repair crews before the agency brains can finish the maps. You just happen to be passing through, trying to find some money to get home after an overly expensive spring break...
A golygon is a possibly self-intersecting figure formed by increasing, integer-length edges perpendicular to each other. An edge must be one unit longer than and at a right angle to the ``previous'' edge. The first edge must be of unit length.
No golygon may pass through an intersection under repair.
The traveller starts (and ends) at (0, 0), the center of the city. The coordinates of the blocked intersections are relative to the center of the city.
Your output consists of a series of golygons, one per line. Each golygon consists of a list of directions (N,S,W, or E) seperated by a comma which indicate the path of the traveler, starting from the beginning of the expedition. Following the list of golygons, output the number of golygons found for the city.
A diagram of the city used in the example, along with the possible golygon, is given in the figure below.
Only solvable cities will be tested.
Example 3:
Enter length of longest edge: 7
Enter number of blocked intersections: 2
Enter blocked intersections: 5 7
Enter blocked intersections: 8 7
N,E,S,E,S,W,N
S,E,N,E,N,W,S
Found 2 golygon(s).
Example 4:
Enter length of longest edge: 15
Enter number of blocked intersections: 4
Enter blocked intersections: 14 14
Enter blocked intersections: 16 16
Enter blocked intersections: 15 16
Enter blocked intersections: 16 15
N,E,S,W,S,E,N,E,S,W,N,E,N,W,S
W,S,E,N,E,S,W,S,E,N,W,S,W,N,E
Found 2 golygon(s).
Example 5:
Enter length of longest edge: 16
Enter number of blocked intersections: 3
Enter blocked intersections: 15 16
Enter blocked intersections: 16 17
Enter blocked intersections: 14 14
N,E,S,E,S,E,N,W,N,E,S,W,S,E,N,W
N,E,S,E,S,E,N,W,S,E,N,W,N,E,S,W
N,E,S,E,N,E,S,W,S,E,N,W,S,E,N,W
N,W,S,E,S,E,N,W,N,W,S,E,S,E,N,W
N,W,S,E,N,E,S,W,S,W,N,E,S,E,N,W
N,W,S,E,N,W,S,E,S,E,N,W,S,E,N,W
Found 6 golygon(s).