{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe Eight Puzzle, among other sliding-tile puzzles, is one of the famous problems in artificial intelligence. Along with chess, tic-tac-toe and backgammon, it has been used to study search algorithms.\u003c/p\u003e\u003cp\u003eThe Eight Puzzle can be generalized into an \u003ci\u003eM\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e Puzzle where at least one of \u003ci\u003eM\u003c/i\u003e and \u003ci\u003eN\u003c/i\u003e is odd. The puzzle is constructed with \u003ci\u003eMN\u003c/i\u003e − 1 sliding tiles with each a number from 1 to \u003ci\u003eMN\u003c/i\u003e − 1 on it packed into a \u003ci\u003eM\u003c/i\u003e by \u003ci\u003eN\u003c/i\u003e frame with one tile missing. For example, with \u003ci\u003eM\u003c/i\u003e \u003d 4 and \u003ci\u003eN\u003c/i\u003e \u003d 3, a puzzle may look like:\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003cp\u003eLet\u0027s call missing tile 0. The only legal operation is to exchange 0 and the tile with which it shares an edge. The goal of the puzzle is to find a sequence of legal operations that makes it look like:\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003cp\u003eThe following steps solve the puzzle given above.\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"0\" width\u003d\"600\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003eSTART\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\" id\u003d\"table1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003eDOWN\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003eLEFT\u003cbr\u003e⇒\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003eUP\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\" id\u003d\"table5\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e\u003cspan lang\u003d\"en-us\"\u003e…\u003c/span\u003e\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd height\u003d\"20\" align\u003d\"center\" colspan\u003d\"9\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003eRIGHT\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003eUP\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\" id\u003d\"table7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003eUP\u003cbr\u003e⇒\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003eLEFT\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\" id\u003d\"table2\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003eGOAL\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003cp\u003eGiven an \u003ci\u003eM\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e puzzle, you are to determine whether it can be solved.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input consists of multiple test cases. Each test case starts with a line containing \u003ci\u003eM\u003c/i\u003e and \u003ci\u003eN\u003c/i\u003e (2 \u003cspan lang\u003d\"en-us\"\u003e≤ \u003ci\u003eM\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e ≤ 999). This line is followed by \u003ci\u003eM\u003c/i\u003e lines containing \u003ci\u003eN\u003c/i\u003e numbers each describing an \u003ci\u003eM\u003c/i\u003e ×\u003c/span\u003e \u003ci\u003eN\u003c/i\u003e puzzle.\u003c/p\u003e\u003cp\u003eThe input ends with a pair of zeroes which should not be processed.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one line for each test case containing a single word \u003ctt\u003eYES\u003c/tt\u003e if the puzzle can be solved and \u003ctt\u003eNO\u003c/tt\u003e otherwise.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\r\n1 0 3\r\n4 2 5\r\n7 8 6\r\n4 3\r\n1 2 5\r\n4 6 9\r\n11 8 10\r\n3 7 0\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\r\nNO\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}