#include "infection.h"
#include <bits/stdc++.h>
std::vector<std::vector<int> > adj;
std::vector<std::vector<int> > path;
std::vector<bool> visited;
void dfs(std::vector<int> currPath, int curr, int finish)
{
    if(curr == finish)
    {
        path.push_back(currPath);
//        for(int i = 0; i < currPath.size(); i++)
//        {
//            std::cout<<currPath[i]<<" ";
//        }
//        std::cout<<std::endl;
    }
    else
    {
        for(auto x: adj[curr])
        {
            if(!visited[x])
            {
                //std::cout<<adj[curr][i]<<std::endl;
                currPath.push_back(x);
                visited[x] = true;
                dfs(currPath, x, finish);
                currPath.pop_back();
                visited[x] = false;
            }
        }
    }
}
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)
{
    long long N = R.size() + 1;
    long long M = D.size();
    adj.resize(N);
    visited.resize(N);
    //path.resize(M);
    for(int i = 0; i < R.size(); i++)
    {
        adj[R[i].first].push_back(R[i].second);
        adj[R[i].second].push_back(R[i].first);
//        std::cout<<R[i].first<<" "<<R[i].second<<std::endl;
    }
    std::vector<int> currPath;
    int maxDays = 0;
    for(int i = 0; i < M; i++)
    {
        currPath.clear();
        visited.clear();
        visited[S[i]] = true;
        currPath.push_back(S[i]);
        dfs(currPath, S[i], T[i]);
        if(maxDays < path[path.size() - 1].size())
        {
            maxDays = path[path.size() - 1].size();
        }
    }
    path.resize(M);
    //std::cout<<maxDays<<std::endl;
    std::vector<int> ans;
    ans.resize(M);
    for(int i = 0; i < maxDays; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(path[j].size() > i)
            {
                for(int k = 0; k < j; k++)
                {
                    if(path[k].size() > i && path[j][i] == path[k][i] && (I[j] || I[k]))
                    {
                        I[j] = true;
                        I[k] = true;
                    }
                }
            }
        }
        for(int j = 0; j < N; j++)
        {
            if(I[j] && path[j].size() > i)
            {
                ans[j]++;
            }
        }
    }
    return ans;
}
