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 <utility>
#include <string>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

typedef pair<int,int> P;
const int HMAX = 1005, WMAX = 1005;
int W, H;
P par[HMAX][WMAX];
int lank[HMAX][WMAX];
char field[HMAX][WMAX];
const int DX[4] = {0, 1, 0, -1}, DY[4] = {1, 0, -1, 0};

void init() {
  REP(y, H) REP(x, W) {
    par[y][x] = make_pair(y, x);
    lank[y][x] = 0;
  }
}

P find(P p) {
  if (par[p.first][p.second] == p) {
    return p;
  } else {
    return par[p.first][p.second] = find(par[p.first][p.second]);
  }
}

void unite(P i, P j) {
  i = find(i);
  j = find(j);
  if (i == j) return;
  int li = lank[i.first][i.second], lj = lank[j.first][j.second];
  if (li < lj) {
    par[i.first][i.second] = j;
    return;
  } else {
    par[j.first][j.second] = i;
    if (li == lj)
      lank[i.first][i.second]++;
    return;
  }
}

bool same(P i, P j) {
  return find(i) == find(j);
}

bool islegal(P p) {
  int y = p.first, x = p.second;
  return 0 <= x and x <= W and 0 <= y and y < H;
}

bool is_floor(int y, int x, char c) {
  return islegal(P(y, x)) && field[y][x] == c;
}

int main() {
  cin >> W >> H;
  P start = P(0, 0), tr;
  REP(y, H) {
    string row;
    cin >> row;
    REP(x, W) {
      field[y][x] = row[x];
    }
  }
  init();
  REP(y, H) REP(x, W) {
    P p(y, x);
    if (field[y][x] == '#') continue;
    if (field[y][x] == 't') {
      tr = p;
      field[y][x] = '.';
    }
    REP(i, 4) {
      P n(y + DY[i], x + DX[i]);
      if (is_floor(n.first, n.second, '.')) unite(p, n);
    }
  }
  int t;
  cin >> t;
    if (same(tr, start)) {
      cout << 0 << endl;
      return 0;
    }
  for (int i = 1; i <= t; i++) {
    int x, y;
    cin >> x >> y;
    field[y][x] = '.';
    REP(dir, 4) {
      int ny = y + DY[dir], nx = x + DX[dir];
      if (is_floor(ny, nx, '.')) unite(P(ny,nx),P(y,x));
    }
    if (same(tr, start)) {
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}