J. Robots at Warehouse

Vitaly works at the warehouse. The warehouse can be represented as a grid of n × m cells, each of which either is free or is occupied by a container. From every free cell it’s possible to reach every other free cell by moving only through the cells sharing a side. Besides that, there are two robots in the warehouse. The robots are located in different free cells.
Vitaly wants to swap the robots. Robots can move only through free cells sharing a side, moreover, they can’t be in the same cell at the same time or move through each other. Find out if the swap can be done.

Input

The first line contains two positive integers n and m (2 ≤ n·m ≤ 200000) — the sizes of the warehouse.
Each of the next n lines contains m characters. The j-th character of the i-th line is «.» if the corresponding cell is free, «#» if there is a container on it, «1» if it’s occupied by the first robot, and «2» if it’s occupied by the second robot. The characters «1» and «2» appear exactly once in these lines.

Output

Output «YES» (without quotes) if the robots can be swapped, and «NO» (without quotes) if that can’t be done.

Examples

Input

5 3

1
2
3
4
5
###
#1#
#.#
#2#
###

Output

NO

Input

1
2
3
4
3 5
#...#
#1.2#
#####

Output

YES

题意

在一个屋里面有两个机器人，这两个机器人能否换位置，两个机器人不能重叠，只能上下左右走，空间里有墙‘#’
第一个机器人为‘1’，第二个为‘2’

题解

从第一个机器人开始dfs，走过的地方做标记，每当走到一个点，数这个点周围不是墙的个数，若大于3则一定可以，而且如果没有这样的点，两个机器人在一个环上也可以，即从1出发还能走回1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string>
using namespace std;
vector<string>mp;
int n, m;
struct node {
	int x, y;
	node() {}
	node(int a, int b) { x = a; y = b; }
	bool Cango(int num) {
		if (x >= 0 && x < n)
			if (y >= 0 & y < m)
				if (mp[x][y] != '#')
					return true;
		return false;
	}
	bool operator == (node b) { return x == b.x&&y == b.y; }
	bool operator != (node b) { return !(*this == b); }
	node operator+(node b) { return node(x + b.x, y + b.y); }
}dir[4] = { { -1,0 },{ 0,1 },{ 1,0 },{ 0,-1 } }, st, en;
bool dfs(node t, node fa, int num) {
	mp[t.x][t.y] = num;
	node temp;
	int res = 0;
	int d = 0;
	for (int i = 0; i < 4; i++) {
		temp = t + dir[i];
		if (temp.Cango(num)) {
			if (mp[temp.x][temp.y] != num)
				res += dfs(temp, t, num);
			else if (temp == st && fa != temp)
				return true;
		}
		if (temp.Cango(num + 10)) {
			d++;
			if (d >= 3)res++;
		}
	}
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	string s;
	s.reserve(m);
	mp.reserve(n);
	for (int i = 0; i < n; i++) {
		cin >> s;
		mp.push_back(s);
		for (int j = 0; j < m; j++)
			if (mp[i][j] == '1')
				st.x = i, st.y = j;
			else if (mp[i][j] == '2')
				en.x = i, en.y = j;
	}
	if (dfs(st, st, 1) && mp[en.x][en.y] == 1)printf("YES\n");
	else printf("NO\n"); return 0;
}