#include "infection.h"
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define fr(i,ii,iii) for(int i=ii;i<iii;i++)
using namespace std;
const int N=5003;
int n,m,mxt;
vi v[N];
vector<vi>path;
int inf[N];
bool findpath(int st,int p,int nd,int x){
	if(st==nd){
		path[x].pb(nd);
		return 1;
	}
	for(auto i:v[st]){
		if(i!=p){
			if(findpath(i,st,nd,x)){
				path[x].pb(st);
				return 1;
			}
		}
	}
	return 0;
}
std::vector<int> solve(
    std::vector<std::pair<int, int>> R,
    std::vector<long long> D,
    std::vector<int> S,
    std::vector<int> T,
    std::vector<bool> I
) {
	n=R.size()+1;m=D.size();
	path.resize(m);
    for(auto i:R){
    	v[i.ff].pb(i.ss);
    	v[i.ss].pb(i.ff);
	}
	vi ans(m);
	fr(i,0,m){
		findpath(S[i],-1,T[i],i);
		mxt=max(mxt,(int)path[i].size());
		if(I[i])ans[i]=path[i].size();
		else ans[i]=0;
		//reverse(path[i].begin(),path[i].end());
	}
	return ans;
//	fr(i,0,m)if(I[i])inf[i]++;
//	vector<bool>infected(n);
//	fr(i,0,mxt){
//		fr(j,0,n)infected[j]=0;
//		fr(j,0,m){
//			if(path[j].size()<=i){
//				continue;
//			}
//			if(inf[j]){
//				infected[path[j][i]]=1;
//			}
//		}
//		fr(j,0,m){
//			if(path[j].size()<=i)continue;
//			if(infected[path[j][i]])inf[j]++;
//		}
//	}
//	fr(i,0,m)if(I[i])inf[i]--;
//	vi ans(m);
//	fr(i,0,m)ans[i]=inf[i];
//	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;
}
*/
/*
9 5
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
0 0 5 1
0 5 7 0
0 5 7 0
0 7 8 0
0 0 1 0

12 5
0 1
0 2
1 3
3 4
4 5
2 6
2 7
7 8
8 9
8 10
6 11
0 0 5 1
0 3 7 0
0 11 8 0
0 10 9 1
0 1 11 0
*/