{"trustable":false,"sections":[{"title":"","value":{"format":"PLAIN","content":"Imagine a country whose cities have all their streets laid out in a regular grid. Now suppose that a tourist with an obsession for geometry is planning expeditions to several such cities.\n\nStarting each expedition from the central cross-roads of a city, the intersection labelled (0,0), our mathematical visitor wants to set off north, south, east or west, travel one block, and view the sight sat the intersection (0,1) after going north, (0,-1) after going south, (1,0) after going east or (-1,0) after going west. Feeling ever more enthused by the regularity of the city, our mathematician would like to walk a longer segment before stopping next, going two blocks.\n\n\nWhat\u0027s more, our visitor doesn\u0027t want to carry on in the same direction as before, nor wishes to double back, so will make a 90 o turn either left or right. The next segment should be three blocks,again followed by a right-angle turn, then four, five, and so on with ever-increasing lengths until finally,at the end of the day, our weary traveller returns to the starting point, (0,0).\n\nThe possibly self-intersecting gure described by these geometrical travels is called a golygon.\n\nUnfortunately, our traveller will making these visits in the height of summer when road works will disrupt the stark regularity of the cities\u0027 grids. At some intersections there will be impassable obstructions. Luckily, however, the country\u0027s limited budget means there will never be more than 50 road works blocking the streets of any particular city. In an attempt to gain accountability to its citizens, the city publishes the plans of road works in advance. Our mathematician has obtained a copy of these plans and will ensure that no golygonal trips get mired in molten tar.Write a program that constructs all possible golygons for a city.\n\nInput\n\nSince our tourist wants to visit several cities, the input file will begin with a line containing an integer specifying the number of cities to be visited.\n\nFor each city there will follow a line containing a positive integer not greater than 20 indicating the length of the longest edge of the golygon. That will be the length of the last edge which returns the traveler to (0,0). Following this on a new line will be an integer from 0 to 50 inclusive which indicates how many intersections are blocked. Then there will be this many pairs of integers, one pair per line,each pair indicating the x and y coordinates of one block age.\n\nOutput\n\nFor each city in the input, construct all possible golygons. Each golygon must be represented by asequence of characters from the set {n,s,e,w} on a line of its own. Following the list of golygons should be a line indicating how many solutions were found. This line should be formatted as shown in the example output. A blank line should appear following the output for each city.\n\nNote:See on the right the diagram of the 1st City\n\nSample Input\n\n2\n8\n2\n-2 0\n6 -2\n8\n2\n2 1\n-2 0\n\nSample Output\n\nwsenenws\nFound 1 golygon(s).\n\nFound 0 golygon(s).\n\n想象一下,在一个国家的城市里,所有的街道都有规律地排列成一个网格。现在假设一个对几何学有痴迷的游客正在计划对几个这样的城市进行考察。\n\n每一次考察都从一个城市的中心十字路口开始,也就是标示为(0,0)的十字路口,我们的数学游客要向北、向南、向东或向西出发,走一个街区,向北走后看到十字路口(0,1),向南走后看到(0,-1),向东走后看到(1,0),向西走后看到(-1,0)。我们的数学家感到越发为这个城市的规律性所陶醉,他想走一段较长的路,然后再停下来,走两个街区。\n\n\n更重要的是,我们的来访者不想继续沿着之前的方向走,也不希望双倍返回,所以会向左或向右转90o。下一段应该是3个街区,同样是直角转弯,然后是4个,5个,以此类推,长度不断增加,直到最后,在一天结束时,我们疲惫的旅行者回到起点,(0,0)。\n\n这些几何旅行所描述的可能是自相交的图形被称为golygon。\n\n不幸的是,我们的旅行者将在盛夏进行这些访问,届时道路工程将打乱城市网格的规律。在一些十字路口会有无法通行的障碍物。但幸运的是,由于国家预算有限,任何一个城市都不会有超过50个道路工程堵塞街道。 为了对市民负责,城市会提前公布道路工程的计划。我们的数学家已经获得了这些计划的副本,并将确保没有golygonal旅行陷入熔化的焦油中。\n\n输入内容\n\n由于我们的游客想要访问几个城市,输入文件将以一行包含一个整数的行开始,指定要访问的城市数量。\n\n对于每个城市,后面会有一行包含一个不大于20的正整数,表示golygon的最长边的长度。这将是最后一条边的长度,它将旅行者返回到(0,0)。在这之后的新行中,将有一个从0到50(含50)的整数,表示有多少个交叉点被阻断。然后会有这么多对整数,每行一对,每对表示一个街区年龄的x和y坐标。\n\n输出结果\n\n对于输入的每个城市,构造所有可能的golygons。每个golygon必须用集合{n,s,e,w}中的一个字符序列来表示,并自成一行。 在多角形列表之后,应该有一行表示找到了多少个解,这一行的格式如图所示。这一行的格式应该如示例输出所示。在每个城市的输出后面应该出现一行空白。\n\n注:请看右边的第1个城市的图。\n\n样品输入\n\n2\n8\n2\n-2 0\n6 -2\n8\n2\n2 1\n-2 0\n\n采样输出\n\nwsenenws\n找到1个golygon(s)。\n\n找到0个golygon(s)。"}}]}