#include<bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using Mat = vector<vi>;

const int N = 150005;
int lg2[N];

void init() {
	lg2[1] = 0;
	for (int i=2; i<N; i++) {
		lg2[i] = lg2[i / 2] + 1;
	}
}

Mat adj;
vi depth, order, parent;

void dfs(int node, int p) {
//	cout << node << endl;
	parent[node] = p;
	order.pb(node);
	for (int v : adj[node]) {
		if (v == p) continue;
		depth[v] = depth[node] + 1;
		dfs(v, node);
		order.pb(node);
	}
}

int op(int a, int b) {
	return depth[a] < depth[b] ? a: b;
}

struct Table {
	int n, LOG;
	Mat table;
	Table(vi& order) : n(order.size()), LOG(lg2[n] + 1), table(LOG, vi(n)) {
		for (int i=0; i<n; i++) {
			table[0][i] = order[i];
		}
		
		for (int j=1; j<LOG; j++) {
			for (int i=0; i<n; i++) {
				if (i + (1 << (j - 1)) >= n) break;
				table[j][i] = op(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]);
			}
		}
	}
	
	int query(int l, int r) {
		int k = lg2[r - l + 1];
		return op(table[k][l], table[k][r - (1 << k) + 1]);
	}
};

vi solve(vector<pii> R, vll D, vi S, vi T, vector<bool> I) {
	init();
//	cout << "A" << endl;
	
	int n = R.size() + 1;
	int m = D.size();
	adj.resize(n);
	for (auto [a, b] : R) {
		adj[a].pb(b);
		adj[b].pb(a);
//		cout << a << ' ' << b << endl;
	}
	
	
//	cout << "DFS" << endl;
	
	depth.resize(n);
	parent.resize(n);
	dfs(0, -1);
	
//	cout << "INDS" << endl;
	
	vi inds(n, -1);
	for (int i=0; i<order.size(); i++) {
		if (inds[order[i]] == -1) inds[order[i]] = i;
	}
//	cout << "B" << endl;
	
	map<ll, map<int, vi>> days;
	vll days2;
	Table table(order);
	
//	cout << "MAIN" << endl;
	
	for (int i=0; i<m; i++) {
		int l = inds[S[i]];
		int r = inds[T[i]];
		if (l > r) swap(l, r);
		
		int lca = table.query(l, r);
		
		ll d = D[i];
		int cur = S[i];
		while (cur != lca) {
			days[d][cur].pb(i);
			cur = parent[cur];
			days2.pb(d);
			d++;
		}
			
		days[d][lca].pb(i);
		cur = T[i];
		days2.pb(d);
		
		d += depth[T[i]] - depth[lca];
		while (cur != lca) {
			days[d][cur].pb(i);
			cur = parent[cur];
			days2.pb(d);
			d--;
		}
	}
	
//	cout << "C" << endl;
	
	sort(all(days2));
	days2.erase(unique(all(days2)), days2.end());
	
	vi ans(m);
	for (ll d : days2) {
		for (int node = 0; node < n; node++) {
			bool has = false;
			vi& row = days[d][node];
			for (int p : row) {
				has = I[p];
				if (has) break;
			}
			if (!has) continue;
			for (int p : row) {
				ans[p]++;
				I[p] = true;
			}
		}
	}
	
//	cout << "D" << endl;
//	
//	for (int d : ans) {
//		cout << d << endl;
//	}
	
	return ans;
}
/*
int main() {
	int n, m;
	cin >> n >> m;
	vector<pii> R(n - 1);
	for (int i=0; i<n-1; i++) {
		cin >> R[i].first >> R[i].second;
	}
	vll D(m);
	vi S(m), T(m);
	vector<bool> I(m);
	for (int i=0; i<m; i++) {
		int x;
		cin >> D[i] >> S[i] >> T[i] >> x;
		I[i] = x;
	}
	
	solve(R, D, S, T, I);
}
/*

9 5
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
1 0 5 1
3 5 7 0
4 5 7 0
8 7 8 0
10 0 1 0

*/