有一个由 $N \times M$ 个格子组成的网格。网格中的一些格子是被阻塞、无法通行的，另一些格子是可以通行的。现在要按照如下规则，对可以通行的格子进行涂色。

1. 在 $N \times M$ 个格子中选择一个作为当前格子并开始。起始的当前格子可以是任意一个可通行的格子。
2. 从当前格子选择一个方向（上 / 下 / 左 / 右之一），并持续向该方向移动，直到到达网格的左 / 右 / 上 / 下边界，或者即将移动到的格子是被阻塞的为止。注意，中途不能停下。
3. 停止时，如果移动方向是水平方向（左或右），则所有经过的格子都会被涂成黄色，起始格子也会被涂成黄色。如果移动方向是竖直方向（上或下），则所有经过的格子都会被涂成蓝色，起始格子也会被涂成蓝色。（即使由于所选方向的相邻格子立即被阻塞而一步也无法移动，也视为对起始格子进行涂色。）
4. 如果所有可通行的格子都至少被涂过一次黄色，并且也至少被涂过一次蓝色，则成功并结束。
5. 否则，从步骤 2 结束时停止的格子（即最后一个能够到达的格子）开始，再次重复步骤 2–4。即使无限次重复该过程，如果仍然无法使所有可通行的格子都至少被涂过一次黄色且至少被涂过一次蓝色，则判定为失败。

例如，考虑如下示例。在一个 $2 \times 3$ 的网格中，所有格子都是可通行的。如果从最左上角 $(0,0)$ 出发，如左图和中图所示，无论如何移动，都无法使所有可通行的格子至少被涂过一次蓝色且至少被涂过一次黄色。相反，如果从 $(0,1)$ 出发，并如右图所示移动，则可以使所有可通行的格子至少被涂过一次蓝色并且至少被涂过一次黄色。

给定网格的大小和布局，判断是否存在一种方法，可以将所有可通行的格子都同时用蓝色和黄色涂到。为了解决该问题，你需要实现如下函数：

• int yellowblue( int N, int M, vector<string> V );

该函数只会被调用一次。$N$ 和 $M$ 表示网格的大小。$V$ 是一个长度为 $N$ 的字符串数组（vector），每个字符串的长度为 $M$。如果网格中第 $(i, j)$ 个格子是可通行的，则 V[i] 的第 $j$ 个字符是 '.'，如果是被阻塞的格子，则为 '#'。如果存在某个起始位置，使得可以将网格中所有可通行的格子至少涂一次蓝色、且至少涂一次黄色，则返回 1，否则返回 0。

实现细节

你必须提交一个名为 grid.cpp 的文件，该文件中需要实现如下函数：

• int yellowblue( int N, int M, vector<string> V );

该函数应当按照上文所述的方式运行。当然，你可以在内部实现并使用其他辅助函数。提交的代码不得进行输入输出操作，也不得访问其他文件。

给定的评测程序（grader）会按照如下格式读取输入：

• 第 1 行：$N\ M$ （$N$：网格的行数，$M$：网格的列数）
• 第 $2+i$ 行（$0 \le i \le N-1$）：一个由 '.' 和 '#' 组成、长度为 $M$ 的字符串。如果该字符串的第 $j$ 个字符（$1 \le j \le M$）是 '.'，则网格中的 $(i, j-1)$ 号格子是可通行的；如果是 '#'，则该格子是被阻塞的。

评测程序会输出你在 yellowblue() 函数中返回的值。

限制

• $1 \le N, M \le 1000$
• 整个网格中至少存在一个可通行的格子

子任务

• 子任务 1（30 分）：$N, M \le 50$
• 子任务 2（70 分）：无额外限制

样例数据

输入样例 1

1 1
.

输出样例 1

1

输入样例 2

2 3
...
...

输出样例 2

1

输入样例 3

3 3
...
..#
.##

输出样例 3

1

输入样例 4

3 3
.##
#..
#..

输出样例 4

0