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 <string>
#include <vector>
using namespace std;

struct UF {
    vector<int> v;
    UF(int n) : v(n,-1) {;}
    int root(int x) { return (v[x] < 0) ? x : v[x] = root(v[x]); }
    bool same(int v,int u) { return root(v) == root(u); }
    bool unite(int x,int y) {
        x = root(x); y = root(y);
        if(x != y) {
            if(v[y] < v[x]) swap(x,y);
            v[x] += v[y]; v[y] = x;
        }
        return x != y;
    }
};

const int MAXH = 1000;
int w,h;
string in[MAXH];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

inline int idx(int x,int y) { return y*w+x; }
inline bool ok(int x,int y) { return x >= 0 && x < w && y >= 0 && y < h; }

int main() {
    cin>>w>>h;
    for(int i=0; i<h; ++i) cin>>in[i];
    UF uf(w*h);

    int tx,ty;
    for(int i=0; i<h; ++i)
        for(int j=0; j<w; ++j) {
            if(in[i][j] == 't') tx=j, ty=i;
            if(in[i][j] != '#') {
                for(int k=0; k<4; ++k)
                    if(ok(j+dx[k],i+dy[k]) && in[i+dy[k]][j+dx[k]] != '#')
                        uf.unite(idx(j,i),idx(j+dx[k],i+dy[k]));
            }
        }

    int n = 0,ans=1<<29,x,y;
    cin>>n;
    for(int i=0; i<n; ++i) {
        if(uf.same(idx(0,0),idx(tx,ty))) ans = min(ans,i);
        cin>>x>>y;
        if(in[y][x] == '#') {
            for(int k=0; k<4; ++k)
                if(ok(x+dx[k],y+dy[k]) && in[y+dy[k]][x+dx[k]] != '#')
                    uf.unite(idx(x,y),idx(x+dx[k],y+dy[k]));
            in[y][x] = '.';
        }
    }

    if(uf.same(idx(0,0),idx(tx,ty))) ans = min(ans, n);
    if(ans == 1<<29) ans = -1;
    cout<<ans<<endl;
}