Firsly ,

• I am finding all cycles in graph
• For all nodes , keeping track of in which cycle it belongs to and what is the node no. in that cycle for that node.
• erasing all cycle causing edges
• then applying binary lifting on inverted tree.

now ready to answer queries.

• if given starting node is involved any cycle then ending node should also be in same cycle. otherwise ans is -1.

  If both are in same cycle then we can compute distance between them in O(1) using node nos. of both node.

• Now , if Starting node is not in any cycle.

  Then ending node must be ancestor of it otherwise ans is -1 (not reachable)
  
  Now as ending node is ancestor of starting node (talking in inverted tree) , we can walk upto that node 
  and compute desired no. of jumps.
  
   It will be in O(logn).

#include<bits/stdc++.h>
#define maxn 300005
#define ll long long int
using namespace std;

// https://cses.fi/problemset/task/1160/

set<int> par[maxn];
vector<int> nxt(maxn);
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);

vector<bool> v1(maxn,false),v2(maxn,false);
vector<vector<int>> cycle;
vector<int> tmp;
int cyc_id=0;
int nn=0;
int start=-1;

vector<int> tin(maxn),tout(maxn);
int tem=0;
vector<int> latkav;

void dfs(int n)
{
    v1[n]=true;
    int c=nxt[n];
    if(v1[c] && !v2[c])
    {
        nxt[n]=-1;
        par[c].erase(n);
        latkav.push_back(n);
        start=c;
    }
    if(!v1[c]) dfs(c);

    if(start!=-1)
    {
        tmp.push_back(n);
        kai_cyc[n]=cyc_id;
        kyo_node[n]=nn++;
        if(n==start) 
        {
            cycle.push_back(tmp);
            start=-1;
            tmp.clear();
            nn=0;
            cyc_id++;
        }
    }
    v2[n]=true;
}

vector<vector<int>> up;
int mxh;

void dfs1(int n,int p)
{
    tin[n]=tem++;
    
    up[n][0]=p;
    for(int i=1;i<=mxh;i++)
    {
        if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }
    }

    for(int c:par[n]) dfs1(c,n);
    tout[n]=tem++;
}

bool isanc(int u,int v)
{
    return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}

int main()
{
    jaldi

    int n,q;
    cin>>n>>q;
    for(int i=1,x;i<=n;i++)
    {
        cin>>x;
        nxt[i]=x;
        par[x].insert(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(!v1[i]) dfs(i);
    }

    //for(vector<int> v:cycle) { deb(v); } //if in same cycle then o(1) ans, else binary lifting

    mxh=ceil(log2(n));
    up.assign(n+1,vector<int>(mxh+1,-1));

    for(int x:latkav) dfs1(x,-1);

    while(q--)
    {
        int start,end;
        cin>>start>>end;

        if(start==end) { cout<<"0\n"; continue; }

        if(kai_cyc[start]!=-1)
        {
            if(kai_cyc[start]==kai_cyc[end]) 
            {
                int s=kyo_node[start];
                int e=kyo_node[end];
                int sz=cycle[kai_cyc[start]].size();
                cout<<(s-e+sz)%sz<<"\n"; 
            }
            else { cout<<"-1\n"; }
            continue;
        }
        if(isanc(end,start))
        {
            int jump=0;
            for(int i=mxh;i>=0;i--)
            {
                if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }
            }
            cout<<jump+1<<"\n";
        }
        else { cout<<"-1\n"; }
    }
    return 0;
}

#include<bits/stdc++.h>

#define maxn 200005
#define ll long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

// https://cses.fi/problemset/task/1160/

set<int> par[maxn];
vector<int> nxt(maxn);
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);

vector<bool> v1(maxn,false),v2(maxn,false);
vector<vector<int>> cycle;
vector<int> tmp;
int cyc_id=0;
int nn=0;
int start=-1;

vector<int> tin(maxn),tout(maxn);
int tem=0;
vector<int> latkav;

void dfs(int n)
{
    v1[n]=true;
    int c=nxt[n];
    if(v1[c] && !v2[c])
    {
        par[c].erase(n);
        latkav.push_back(n);
        start=c;
    }
    if(!v1[c]) dfs(c);

    if(start!=-1)
    {
        tmp.push_back(n);
        kai_cyc[n]=cyc_id;
        kyo_node[n]=nn++;
        if(n==start) 
        {
            cycle.push_back(tmp);
            start=-1;
            tmp.clear();
            nn=0;
            cyc_id++;
        }
    }
    v2[n]=true;
}

vector<vector<int>> up;
int mxh;

void dfs1(int n,int p)
{
    tin[n]=tem++;
    
    up[n][0]=p;
    for(int i=1;i<=mxh;i++)
    {
        if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }
    }

    for(int c:par[n]) dfs1(c,n);
    tout[n]=tem++;
}

bool isanc(int u,int v)
{
    return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}

int main()
{
    fastio

    int n,q;
    cin>>n>>q;
    for(int i=1,x;i<=n;i++)
    {
        cin>>x;
        nxt[i]=x;
        par[x].insert(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(!v1[i]) dfs(i);
    }

    mxh=ceil(log2(n));
    up.assign(n+1,vector<int>(mxh+1,-1));

    for(int x:latkav) dfs1(x,-1);

    while(q--)
    {
        int start,end;
        cin>>start>>end;

        if(start==end) { cout<<"0\n"; continue; }

        if(kai_cyc[start]!=-1)
        {
            if(kai_cyc[start]==kai_cyc[end]) 
            {
                int s=kyo_node[start];
                int e=kyo_node[end];
                int sz=cycle[kai_cyc[start]].size();
                cout<<(s-e+sz)%sz<<"\n"; 
            }
            else { cout<<"-1\n"; }
            continue;
        }
        if(isanc(end,start))
        {
            int jump=0;
            for(int i=mxh;i>=0;i--)
            {
                if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }
            }
            cout<<jump+1<<"\n";
        }
        else
        {
            int jump=0;
            for(int i=mxh;i>=0;i--)
            {
                if(up[start][i]!=-1) { start=up[start][i]; jump+=1<<i;}
            }
            if(kai_cyc[start]==kai_cyc[end])
            {
                int s=kyo_node[start];
                int e=kyo_node[end];
                int sz=cycle[kai_cyc[start]].size();
                cout<<((s-e+sz)%sz+jump)<<"\n"; 
            }
            else { cout<<"-1\n"; }
        }
    }
    return 0;
}

You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).

Your task is to process q queries of the form: when you begin on planet x and travel through k teleporters, which planet will you reach?

n , q can be upto 2.10^5.
k can be upto 10^9.

You are given a directed weighted graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle.

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
#define mod 1000000007 
#define check exit(0)
#define nl cout<<endl;
#define inp 30000
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define trace(x) cerr<<#x<<" : "<<x<<endl;
#define deb(v) for(int i=0;i<v.size();i++) {cout<<v[i]; (i==v.size()-1) ? cout<<"\n":cout<<" "; }
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
using namespace __gnu_pbds;
using namespace std;
 
vector<pair<ll,ll>> g[inp];
vector<ll> weight(inp,0); 
 
vector<bool> vis1(inp,false),vis2(inp,false);
vector<ll> par(inp);
vector<ll> ans;
 
void dfs(ll n,ll tot)
{
    vis1[n]=true;
    weight[n]=tot;
 
    for(pair<ll,ll> c:g[n])
    {
        if(vis1[c.first] && !vis2[c.first]) // cycle detected
        {
            ll tmp = weight[n]-weight[c.first] + c.second; //weight of cycle

            if(tmp<0)
            {   
                ans.push_back(c.first);
                while(n!=c.first)
                {
                    ans.push_back(n);
                    n=par[n];
                }
                ans.push_back(c.first);

                reverse(ans.begin(),ans.end());
                
                cout<<"YES\n";
                for(int x:ans) cout<<x<<" ";
                check;
            }
        }
        if(!vis1[c.first]) { par[c.first]=n; dfs(c.first , tot+c.second); }
    }
 
    vis2[n]=true; //completely explored node
}
 
int main()
{
    jaldi
 
    ll n,m; //vertices & edges
    cin>>n>>m;
 
    vector<vector<ll>> arr(n+1,vector<ll>(n+1,LLONG_MAX)); // adj. matrix so that we can select edge with 
                                                           // minimum weight
 
    for(ll i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        arr[u][v]=min(arr[u][v],w);
    }
 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(arr[i][j]<LLONG_MAX) { g[i].push_back({j,arr[i][j]}); } //preparing adj. list
        }
    }
 
    for(int i=1;i<=n;i++)
    {
        if(!vis1[i])
        {
            dfs(i,0);
        }
    }
 
    cout<<"NO\n"; //Neg. cycle not found
 
    return 0;
}

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
#define mod 1000000007 
#define check exit(0)
#define nl cout<<endl;
#define inp 30000
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define trace(x) cerr<<#x<<" : "<<x<<endl;
#define deb(v) for(int i=0;i<v.size();i++) {cout<<v[i]; (i==v.size()-1) ? cout<<"\n":cout<<" "; }
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
using namespace __gnu_pbds;
using namespace std;
 
vector<ll> weight(inp,0);
 
vector<pair<ll,ll>> g[inp];
 
vector<bool> vis1(inp,false),vis2(inp,false);
vector<ll> par(inp);
vector<ll> ans;
 
void dfs(ll n,ll tot)
{
    vis1[n]=true;
    weight[n]=tot;
 
    for(pair<ll,ll> c:g[n])
    {
        if(vis1[c.first] && !vis2[c.first]) // cycle detected
        {
            ll tmp = weight[n]-weight[c.first] + c.second;
            if(tmp<0)
            {   
                ans.push_back(c.first);
                while(n!=c.first)
                {
                    ans.push_back(n);
                    n=par[n];
                }
                ans.push_back(c.first);
                reverse(ans.begin(),ans.end());
                cout<<"YES\n";
                deb(ans);
                check;
            }
        }
        if(!vis1[c.first]) { par[c.first]=n; dfs(c.first , tot+c.second); }
    }
 
    vis2[n]=true;
}
 
int main()
{
    jaldi
 
    ll n,m;
    cin>>n>>m;
 
    vector<vector<ll>> arr(n+1,vector<ll>(n+1,LLONG_MAX));
 
    for(ll i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        arr[u][v]=min(arr[u][v],w);
    }
 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(arr[i][j]<LLONG_MAX) { g[i].push_back({j,arr[i][j]}); }
        }
    }
 
    for(int i=1;i<=n;i++)
    {
        if(!vis1[i])
        {
            dfs(i,0);
        }
    }
 
    cout<<"NO\n";
 
    return 0;
}