#include <iostream>
#include <fstream>
#include <vector>

#include <cstdlib>

using namespace std;


int dijkstra(vector<vector<int>> adj, int a, int b, int n) {
    a -= 1;
    b -= 1;
    const int inf = 2147483647;
    vector<int> dist(n);
    vector<bool> solved(n, false);

    for (int i = 0; i < n; i++) {
        dist[i] = inf;
    }


    int current_node = a;

    solved[current_node] = true;
    dist[current_node] = 0;

    vector<int> to_resolve;
    do {
        to_resolve.clear();

        cout << "Sono al nodo " << (current_node+1) << endl;
        // Cerco il nodo meno costoso
        for (int i = 0; i < n; i++) {
            // Aggiungo solo quelli non ancora risolti e con un costo >= 0
            // cout << "solved["<<(i+1)<<"] = " << solved[i] << endl;
            if (solved[i]) continue;
            if (adj[current_node][i] >= 0) {
                to_resolve.push_back(i);
                cout << "Potrei andare al nodo " << (i+1) << endl;
            }
        }

        /* Calcolo il costo per spostarsi a quei nodi */
        int chosen = -1;
        int chosen_cost = inf;
        for (int i = 0; i < to_resolve.size(); i++) {
            int cost = adj[current_node][to_resolve[i]];
            int total_cost = dist[current_node] + cost;

            cout << "Per andare al nodo " << (to_resolve[i]+1) << " il costo: " << cost << ", il costo totale: " << total_cost << endl;
            //cout << "dist[" << to_resolve[i]+1 << "] = " << dist[to_resolve[i]] << " updated to " << total_cost << endl;
            if (dist[to_resolve[i]] > total_cost)
                dist[to_resolve[i]] = total_cost;

            /* Salvo il meno costoso */
            if (chosen == -1 || cost < chosen_cost) {
                chosen = to_resolve[i];
                chosen_cost = total_cost;
            }
        }
        cout << "Ho scelto " << chosen+1 << " al costo di " << chosen_cost << endl;
        solved[chosen] = true;

        current_node = chosen;

        cout << endl << endl;

    } while (current_node != b);

    for (int i = 0; i < n; i++) {
        cout << "dist[" << i+1 << "] = " << dist[i] << endl;
    }

    cout << "fine" << endl;
    return dist[b];
}

int main() {
    int N, A, B; // Nodes, Cold Route, Hot Route

    ifstream input("input.txt", ios::in);
    input >> N >> A >> B;

    vector<vector<int>> adj(N);
    for (int i = 0; i < N; i++) {
        vector<int> row (N, -1);
        adj[i] = row;
    }

    for(int i = 0, s, d; i < A+B; i++) {
        input >> s >> d;
        // cout << s << " - " << d << endl;
        adj[s-1][d-1] = adj[d-1][s-1] = (i >= A ? 1 : 0);
    }

    cout << ' ';
    for (int i = 0; i < N; i++)
        cout << ' ' << (i+1);
    cout << endl;
    for (int i = 0; i < N; i++) {
        cout << (i+1);
        for (int j = 0; j < N; j++)
            cout << ' ' << adj[i][j];
        cout << endl;
    }



    input.close();

    int r = dijkstra(adj, 1, N, N);
    cout << r;

    ofstream o("output.txt");
    o << r;
    o.close();

    return 0;
}