Submission

(PPPP)(PPPPPP)(PPPPPPPPPP)

Score: 100

User: detectives_conan

Problemset: ย้อนศร

Language: cpp

Time: 0.417 second

Submitted On: 2025-01-03 20:13:41

/*
Author : detective conan
problem : ย้อนศร
*/
#include <bits/stdc++.h>
#define int long long

using namespace std;

const bool HAVE_TESTCASE = false;

int n, m, u, v, q, dis[100100];
vector<int> vc[100100], re[100100];

void sol(int a, int b){
    for(int i = 1; i <= n; ++i) dis[i] = 1e9;
    dis[a] = 0;
    deque<int> dq;
    dq.push_front(a);
    while(!dq.empty()){
        int u = dq.front(); dq.pop_front();
        for(auto v:vc[u]){
            if(dis[v] > dis[u]){
                dis[v] = dis[u];
                dq.push_front(v);
            }
        }
        for(auto v:re[u]){
            if(dis[v] > dis[u] + 1){
                dis[v] = dis[u] + 1;
                dq.push_back(v);
            }
        }
    }
    cout << dis[v] << '\n';
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) cin >> u >> v, vc[u].push_back(v), re[v].push_back(u);
    cin >> q;
    while(q--){
        cin >> u >> v;
        sol(u, v);
    }
}

int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    if(HAVE_TESTCASE) cin >> t;
    while(t--) solve();
}