#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
bool visited[3005][3005];
int main() {
    int n, m;
    cin >> n >> m;

    vector<int> graph[n + 5];
    map<vector<int>, bool> pat;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        vector<int> v{a, b, c};// v.push_back(a); v.push_back(b); v.push_back(c);
        pat[v] = true;
    }
    queue<int> q; // FIFO --> first in, first out
    q.push(0); // current node
    q.push(-1); // previous node
    q.push(0); // distance from 0 to current node

    while(!q.empty()) {
        int current_node = q.front();
        q.pop();
        int previous_node = q.front();
        q.pop();
        int distance = q.front();
        q.pop();
        if(current_node == n - 1) {
            cout << distance << endl;
            return 0;
        }
        for(int i = 0; i < graph[current_node].size(); i++) {
            int sosed = graph[current_node][i];
            if(!visited[current_node][sosed] and !pat[{previous_node, current_node, sosed}]) {
                q.push(sosed);
                q.push(current_node);
                q.push(distance + 1);
                visited[current_node][sosed] = true;
            }
        }
    }

    cout << "GRESHKA" << endl;
    return 0;
}