#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;
};

void bfs( int ind, std::vector<int> &S, std::vector<int> &T, vector<int> &way, vector<vector<int>>&edges )
{
    vector<int>dist(edges.size());
    vector<int>pre(edges.size());

    queue<pair<int,int>> q;

    fill_n(dist.begin(), dist.size(), oo);
    dist[S[ind]] = 0;
    q.push({0, S[ind]});
    bool bre = false;
    while ( !q.empty() )
    {
        //cerr << "herrBFS";
        int curr = q.front().second;
        int distCurr = q.front().first;

        q.pop();
        for ( auto next : edges[curr])
        {
            if ( dist[curr] + 1 < dist[next] )
            {
                dist[next]  =dist[curr] +1;
                pre[next] = curr;
                if ( next == T[ind])
                {
                    bre=true;
                    break;
                }
                q.push({ dist[next], next });
            }
        }
        if ( bre ) break;
    }
    int v = T[ind] ;
    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";

    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();
    }
    // 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);

    for ( int today = 0; brended<hora; today++)
    {
        //cerr << today << endl;

        for ( int i=0; i<hora; i++)
        {
            if ( !ready[i] )
            {
                S[i] = ways[i][today];

            }
            else S[i] = -11;

        }
        memset(isCityInfected, false, sizeof(isCityInfected));   /// opt
        for ( int aaa=0; aaa<4; aaa++)
        {
            for ( int i=0; i<hora; i++)
            {
                if ( ready[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=0; i<hora; i++)
        {
            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() - infDate[i];
    }
    return ret; //how many nights each party-goer will spend infected during their party-tour
}
