
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;

int path_length(vvi &graph, int N, int start, int end) {
    if (start == end) return 0;
    vi dist(N, 0);
    vector<bool> visited(N, false);
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dist[neighbor] = dist[node] + 1;
                visited[neighbor] = true;
                q.push(neighbor);
                if (neighbor == end) break;
            }
        }
        if (dist[end] > 0) break;
    }
    return dist[end];
}

vector<int> solve(vector<pii> R, vector<ll> D,
    vector<int> S, vector<int> T, vector<bool> I) {
        int N = R.size() + 1;
        int M = D.size();
        vvi graph(N);
        vi ans(M, 0);
        for (int i = 0; i < R.size(); i++) {
            graph[R[i].first].push_back(R[i].second);
            graph[R[i].second].push_back(R[i].first);
        }
        for (int i = 0; i < M; i++) {
            if (I[i]) {
                ans[i] = path_length(graph, N, S[i], T[i]) + 1;
            }
        }

    return ans;
}


// signed main() {
//     int n, m;

//     std::cin >> n;
//     std::cin >> m;

//     std::vector<std::pair<int, int>> edges = {};
//     std::vector<long long> day;
//     std::vector<int> start;
//     std::vector<int> target;
//     std::vector<bool> infected;

//     for (int i = 0; i < n - 1; i++) {
//         int u, v;
//         std::cin >> u >> v;
//         edges.emplace_back(u, v);
//     }

//     for (int i = 0; i < m; i++) {
//         long long _d, _s, _t, _i;
//         std::cin >> _d >> _s >> _t >> _i;
//         day.push_back(_d);
//         start.push_back(_s);
//         target.push_back(_t);
//         infected.push_back(_i);
//     }

//     const auto ans = solve(edges, day, start, target, infected);
//     for (const auto it : ans) {
//         std::cout << it << std::endl;
//     }

//     return 0;
// }
