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 <algorithm>
#include <string>
using namespace std;
int mp[1002*1002];
char ch[1002*1002];
int w,h,goal;
int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};
int change(int i,int j){
 return i*w+j;
}

int find(int x){
  if(mp[x] == x) return mp[x];
  else return mp[x] = find(mp[x]);
}

void unite(int x,int y){
  x= find(x),y = find(y);
  if(x < y) swap(x,y);
  mp[x] = y;
}

bool same(int x, int y){
  if(find(x) == find(y)) return true;
  return false;
}

int solve(){
  int ans = -1;
  if(same(0,goal)==true)ans = 0;
  int q;
  cin >> q;
  for(int i=1;i<=q;i++) {
    int x,y;
    cin >> x >> y;
    if(ans != -1) continue;
    ch[change(y,x)] = '.';
    for(int j=0;j<4;j++){
      int nx = x+dx[j];
      int ny = y+dy[j];
      int nxy = change(ny,nx);
      if(nx<0||ny<0 || nx>=w || ny>=h ||ch[nxy] == '#') continue;
      unite(change(y,x),nxy);
    }
    if(same(0,goal) == true) ans = i;
  }
  return ans;
}

int main(){
  while(cin >>w >>h){
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)cin >> ch[i*w+j];

    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){
	mp[i*w+j] = i*w+j;
	if(ch[i*w+j] == '#') continue;
	if(ch[i*w+j] == 't') goal = i*w+j;
	for(int k=0;k<2;k++){
	  int nx = j+dx[k];
	  int ny = i+dy[k];
	  int nxy= change(ny,nx);
	  if(nx<0||ny<0||nx>=w||ny>=h||ch[nxy] == '#') continue;
	  unite(change(i,j),nxy);
	}
      }
    cout << solve() <<endl;
  }
  return 0;
}