#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
#define MAXN 5008  ///150008
#define oo INT_MAX
using namespace std;
struct Q
{
    int dist, ind, currV;
};
bool visited[MAXN];
int dist[MAXN];
int pre[MAXN];
void bfs( int ind, std::vector<int> &S, std::vector<int> &T, vector<int> &way, vector<vector<int>>&edges )
{



    queue<int> q;
    memset(visited, false, sizeof(visited));
    memset(dist, -1, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    dist[S[ind]] = 0;
    visited[S[ind]] = true;
    q.push(S[ind]);
    bool bre = false;
    while ( !q.empty() )
    {
        //cerr << "herrBFS";
        int curr = q.front();
        //  int distCurr = q.front().first;

        q.pop();
        for ( auto next : edges[curr])
        {
            if ( visited[next]) continue;

            visited[next] = true;
            dist[next]  =dist[curr] +1;
            pre[next] = curr;
            if ( next == T[ind])
            {
                bre=true;
                break;
            }
            q.push( next );

        }
        if ( bre ) break;
    }
    int v = T[ind] ;
    way.reserve(edges.size());
    while ( v != S[ind] )
    {
        way.push_back(v);
        v = pre[v];
    }
    way.push_back(S[ind]);
    //way.reverse();
    reverse(way.begin(), way.end());

}
void cerrMbool(bool *m, int sz, string name="name")
{
    //cerr << "name: " << name << endl;
    for ( int i=0; i<sz; i++)
    {
        //cerr << m[i] << " ";
    }
    //cerr << endl;

}
void cerrVbool(vector<bool> v, string name="name")
{
    //cerr << "name: " << name << endl;
    for ( auto vv : v)
    {
        //cerr << vv << " ";
    }
    //cerr << endl;

}
void cerrVint(vector<int> v, string name="name")
{
    //cerr << "name: " << name << endl;
    for ( auto vv : v)
    {
        //cerr << vv << " ";
    }
    //cerr << endl;

}
// n*n
void findWays(vector<vector<int>> &ways, std::vector<int> &S, std::vector<int> &T, vector<vector<int>>&edges )
{

    int hora = ways.size();

    for ( int i=0; i<hora; i++)
    {
        bfs(i, S, T, ways[i], edges);
        //cerr << i << endl;
        //cerrVint(ways[i], "ways_i");
    }


}

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
)
{
    vector<int> ret;
    int hora = S.size();
    vector<vector<int>> edges;
    vector<vector<int>> ways;
    ways.resize(hora);
    //cerr << "herr1";
    vector<pair<long long, int>> sorted_days(D.size());

    int n=-1;
    for ( auto [b, e] : R)
    {
        if ( b > n ) n = b;
        if ( e > n) n = e;
    }
    n++;
    edges.resize(n);
    for ( auto [b, e] : R)
    {

        edges[b].push_back(e);
        edges[e].push_back(b);
    }
    //cerr << "herr2";
    findWays(ways, S, T, edges);
    //cerr << "herr3";

    /// CITIES ARE INDEXED FROM 0

    //vector<int> countInfectedInCity(n, 0);
    vector<int> infDate(hora);
    for ( int i=0; i<hora; i++)
    {
        infDate[i] = (I[i])? D[i] : ways[i].size()+D[i];
        sorted_days[i] ={ D[i], i};
    }
    sort(sorted_days.begin(), sorted_days.end());
    int sind = 0;
    // S - now it is in city
    // today

    bool isCityInfected[MAXN]; // memset postoqnno
    //  vector<bool> killed(hora, 0);


    ///!!!!! subtasks 1 and 2   all di=0 ----------------------------------------------------------------
    /// so
    int brended = 0;
    vector<bool> ready(hora, false);
    bool active;
    int START = 0;
    int bractive = 0;
    bool iii = 0;
    for ( long long today = 0; brended<hora; today++)
    {
        //cerr << today << endl;
        active = false;
        bractive = 0;
        iii = false;
        for ( int i=START; i<hora; i++)
        {
            if ( !ready[ sorted_days[i].second   ] )
            {
                if ( today >= sorted_days[i].first)

                {
                    S[sorted_days[i].second] = ways[sorted_days[i].second][today-D[sorted_days[i].second]];
                    active = true;
                    bractive++;
                    iii |= I[sorted_days[i].second  ];
                }
                else break;

            }
            else S[i] = -11;

        }

        if ( !active )
        {
          //  cerr << "not active at day " << today << endl;
            int newday = today;
            while (sind < hora && newday <= today ) newday = sorted_days[sind++].first;
            today = newday - 1;
          //  cerr << "today becomes " << today << endl;
            continue;
        }
        if ( bractive > 1 && iii )
        {
             memset(isCityInfected, false, sizeof(isCityInfected[0])*(n+1));   /// opt
        for ( int aaa=0; aaa<3; aaa++)
        {
            for ( int i=START; i<hora; i++)
            {
                if ( ready[i]) continue;
                if ( today < D[i]) continue;
                if ( isCityInfected[ S[i] ] )
                {
                    if ( !I[i])
                    {
                        I[i] = true;
                        infDate[i] = today;  /// last for can be here
                    }

                }
                else if ( I[i] ) isCityInfected[ S[i] ] = true;
            }
        }
        }

        for ( int i=START; i<hora; i++)
        {
            if ( today < D[i]) continue;
            if ( S[i] == T[i] )
            {
                ready[i] = true;
                brended++;
            }
        }
        //cerrVbool(I, "I");
        //cerrMbool(isCityInfected, n, "isCityInfected");
    }
    //cerrVint(infDate, "infDate");
    ret.resize(hora);
    for ( int i=0; i<hora; i++)
    {
        ret[i] = ways[i].size() + D[i] - infDate[i] ;
    }
    return ret; //how many nights each party-goer will spend infected during their party-tour
}
