DUONG DI NGAN NHAT (Du Tuyen 2 2021)

#define task ""

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstring>
#include <unordered_map>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 5e5 + 5;
constexpr int M = 6e5 + 5;
constexpr int Inf = 1e9 + 7;

struct SegmentTree
{
    int st[M * 4], n;
    SegmentTree()
    {
        fill_n(st, M * 4, Inf);
    }

    void Update(int id, int l, int r, const int &a, const int &b, const int &v)
    {
        if (l > b || r < a)
            return;
        if (l >= a && r <= b)
        {
            st[id] = min(st[id], v);
            return;
        }
        Update(id << 1, l, (l + r) / 2, a, b, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
    }

    void Update(int l, int r, int v)
    {
        Update(1, 1, n, l, r, v);
    }

    int Get(int x)
    {
        int id = 1, l = 1, r = n, ans(Inf);
        while (1)
        {
            ans = min(ans, st[id]);
            if (l == r)
                break;
            if ((l + r) / 2 >= x)
            {
                id = id << 1;
                r = (l + r) / 2;
            }
            else
            {
                id = id << 1 | 1;
                l = (l + r) / 2 + 1;
            }
        }

        return ans;
    }
} f;

vector<int> adj[M], nadj[M];
int n, m, s, t, q, u[N], v[N], a[M];
int d[2][M], in[M], l;
bool vis[M];

void Read()
{
    cin >> n >> m >> s >> t;
    f.n = n + m;

    for (int i = 1; i <= m; ++i)
    {
        cin >> u[i] >> v[i];
        adj[u[i]].emplace_back(n + i);
        adj[n + i].emplace_back(v[i]);
        nadj[v[i]].emplace_back(n + i);
        nadj[n + i].emplace_back(u[i]);
    }

    cin >> q;
}

void BFS(int x, int d[M], vector<int> adj[M])
{
    fill_n(d, M, Inf);
    queue<int> q;
    q.emplace(x);
    d[x] = 0;

    while (!q.empty())
    {
        int c = q.front();
        q.pop();

        for (auto i : adj[c])
            if (d[i] == Inf)
            {
                q.emplace(i);
                d[i] = d[c] + 1;
            }
    }
}

void dfs(int v)
{
    vis[v] = 1;
    for (auto i : adj[v])
        if (!vis[i])
            dfs(i);

    a[++l] = v;
}

void Solve()
{
    BFS(s, d[0], adj);
    BFS(t, d[1], nadj);

    for (int i = 1; i <= n + m; ++i)
        if (!vis[i])
            dfs(i);

    reverse(a + 1, a + n + m + 1);

    for (int i = 1; i <= n + m; ++i)
        in[a[i]] = i;

    for (int i = 1; i <= m; ++i)
        if (d[0][u[i]] < Inf && d[1][v[i]] < Inf)
        {
            int val = d[0][u[i]] + d[1][v[i]] + 2;
            f.Update(in[u[i]] + 1, in[n + i] - 1, val);
            f.Update(in[n + i] + 1, in[v[i]] - 1, val);
        }

    while (q--)
    {
        char t;
        int x;
        cin >> t >> x;
        int v;

        if (t == 'V')
            v = f.Get(in[x]);
        else
            v = f.Get(in[x + n]);

        cout << (v == Inf ? -1 : v / 2) << "\n";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}