Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

10 10
.....#....
.....#....
.....#....
######....
..........
####......
....###...
t..#..####
...##.....
....#...##
3
0 3
0 5
4 6


Output

2
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

int W,H,T;
string field[1000];
bool reached[1000][1000];
int bx[1000], by[1000];

bool bfs(int sx, int sy){

	queue<pair<int, int> > q;
	q.push(make_pair(sx,sy));

	while(!q.empty()){
		pair<int, int> pos = q.front(); q.pop();
		int x = pos.first;
		int y = pos.second;


		if(reached[x][y]) continue;
		reached[x][y] = true;

		if(field[y][x] == 't') return true;

		for(int i=0; i<4; i++) {
			int tx = x + dx[i];
			int ty = y + dy[i];

			if(tx<0||ty<0||tx>=W||ty>=H) continue;
			if(field[ty][tx] == '#') continue;
			if(reached[tx][ty]) continue;

			q.push(make_pair(tx,ty));
		}
	}

	return false;
}

int solve()
{
	int res = 0;

	memset(reached, 0, sizeof(reached));
	if(bfs(0,0)) return 0;

	for(int j=0; j<T; j++)
	{
		res++;
		if(field[by[j]][bx[j]] == '.') continue;
		field[by[j]][bx[j]] = '.';

		for(int i=0; i<4; i++) {
			int tx = bx[j] + dx[i];
			int ty = by[j] + dy[i];

			if(tx<0||ty<0||tx>=W||ty>=H) continue;
			if(reached[tx][ty]) {
				if(bfs(bx[j],by[j])) return res;

				break;
			}
		}
	}

	return -1;
}

int main()
{
	cin >> W >> H;
	for(int i=0; i<H; i++)
		cin >>  field[i];

	cin >> T;
	for(int i=0; i<T; i++)
		cin >> bx[i] >> by[i];

	cout << solve() << endl;
}