{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWhen wondering through the labyrinth, the goal is usually to find some kind of door. Well, not this time.\u003c/p\u003e\u003cp\u003eA labyrinth consists of \u003ci\u003eN\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e cells, each 1 × 1 meter in size. Cells are separated by doors. Each door opens in a specific direction (as shown on the picture):\u003c/p\u003e\u003cp\u003e1. left outwards;\u003cbr\u003e2. left inwards;\u003cbr\u003e3. right outwards;\u003cbr\u003e4. right inwards. \u003c/p\u003e\u003cp\u003eSo a cell can be represented by two numbers describing doors on its eastern and southern sides according to the list above. The doors are just slightly less then 1 meter in width. The traveler in the labyrinth is also slightly less then 1 meter in diameter, so he has following limitations:\u003c/p\u003e\u003cp\u003e* He can not pull doors, only push them.\u003cbr\u003e* After opening the door and entering the cell it leads to, he can not take a turn in the direction where the door opened, because the passage is blocked by the door. Doors have springs and close automatically when traveler leaves the cell. \u003c/p\u003e\u003cp\u003eYour program must find the shortest path for the traveler from north-western cell (1, 1) to south-eastern cell (\u003ci\u003eN\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e).\u003c/p\u003e\u003cimg src\u003d\"CDN_BASE_URL/8ea876810ce9c5d55daab831c9dc4061?v\u003d1714642022\"\u003e "}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eInput file contains labyrinth size \u003ci\u003eN\u003c/i\u003e followed by 2 × \u003ci\u003eN\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e numbers describing doors for each cell row by row. As there are no doors leading outside of labyrinth, values for eastern doors in the last column and southern doors in the last row are zero.\u003c/p\u003e\u003ch4\u003eConstraints\u003c/h4\u003e\u003cp\u003e1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 1000\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput file must contain the shortest path as a list of cell coordinates (column number, then row number), including both (1, 1) and (\u003ci\u003eN\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e) cells. If there are several solutions with the same length, output any one of them. If it is impossible to get to a destination cell, output a singe zero.\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\u003e\u0026lt;b\u0026gt;Sample Input 1\u0026lt;/b\u0026gt;\r\n2\r\n2 3 0 4\r\n1 0 0 0\r\n\u0026lt;b\u0026gt;Sample Input 2\u0026lt;/b\u0026gt;\r\n3\r\n4 3 1 4 0 1\r\n3 3 2 3 0 4\r\n2 0 1 0 0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u0026lt;b\u0026gt;Sample Output 1\u0026lt;/b\u0026gt;\r\n1 1\r\n1 2\r\n2 2\r\n\u0026lt;b\u0026gt;Sample Output 2\u0026lt;/b\u0026gt;\r\n1 1\r\n1 2\r\n2 2\r\n2 1\r\n3 1\r\n3 2\r\n2 2\r\n2 3\r\n3 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"Bold texts appearing in the sample sections are informative and do not form part of the actual data."}}]}