#include "infection.h"
#include <vector>
#include <utility>
using namespace std;

vector<vector<int>> tree, paths;

void getPath(int s, int t, int ind, int prv = -1) {
    if (s == t)
        return;
    for (const auto nxt : tree[s]) {
        if (nxt == prv)
            continue;
        paths[ind].push_back(nxt);
        getPath(nxt, t, ind, s);
        paths[ind].pop_back();
    }
}

vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
    int n = R.size() + 1;
    tree.resize(n + 1), paths.resize(n + 1);
    for (int i = 0; i < n - 1; i++)
        tree[R[i].first].push_back(R[i].second), tree[R[i].second].push_back(R[i].first);
    for (int i = 0; i < n; i++)
        getPath(S[i], T[i], i);
    return I;
}
