CF1236D Alice and the Doll

#### 题目大意 最近，爱丽丝得到了一个新玩偶。它甚至可以走路！ 爱丽丝为玩偶建造了一个迷宫，并想对其进行测试。迷宫具有$n$行和$m$列。有$k$个障碍物，第$i$个障碍物位于单元格（$x_i,y_i$）上，这意味着第$x_i$个行与第$y_i$列相交的单元格上存在一个禁止通过的障碍物。 然而，玩偶有着缺陷。在**同一**单元格（包括起始单元格）中，它最多只能笔直走或右转**一次**。它无法进入有障碍物的单元格或走出迷宫的界限之外。 现在，爱丽丝正在控制娃娃的动作。她将玩偶放入单元格（$1,1$）（即迷宫的左上角）中。最初，玩偶的朝向从$(1,1)$向着$(1,m)$。她想让玩偶**恰好穿过一次所有**单元格而没有障碍，玩偶的行动可以在**任何**地方结束。爱丽丝的想法可以实现吗？

无

无

Here is the picture of maze described in the first example: In the first example, the doll can walk in this way: - The doll is in the cell $ (1, 1) $ , looks to the direction $ 1 $ . Move straight; - The doll is in the cell $ (1, 2) $ , looks to the direction $ 1 $ . Move straight; - The doll is in the cell $ (1, 3) $ , looks to the direction $ 1 $ . Turn right; - The doll is in the cell $ (1, 3) $ , looks to the direction $ 2 $ . Move straight; - The doll is in the cell $ (2, 3) $ , looks to the direction $ 2 $ . Move straight; - The doll is in the cell $ (3, 3) $ , looks to the direction $ 2 $ . Turn right; - The doll is in the cell $ (3, 3) $ , looks to the direction $ 3 $ . Move straight; - The doll is in the cell $ (3, 2) $ , looks to the direction $ 3 $ . Move straight; - The doll is in the cell $ (3, 1) $ , looks to the direction $ 3 $ . The goal is achieved, all cells of the maze without obstacles passed exactly once.