Language: C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[305][305],par[305][305];
vector<int>vt;
void fun(ll n) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            par[i][j]=j;
            if(i==j)
                continue;
            ar[i][j]=INT_MAX;

        }
    }
}

void path(ll u,ll v) {
    //printf("%d",u);
    vt.push_back(u);
    if(u!=v) {
        u=par[u][v];
        //cout<<u<<" "<<v<<endl;
        path(u,v);
    }
}
int main() {
    ll n,edge,u,v,ans,L,cnt;
    ll x,y,z,query;

    scanf("%lld",&n);
    fun(n);
    scanf("%lld %lld",&edge,&L);
    for(int i=1; i<=edge; i++) {
        scanf("%lld %lld %lld",&x,&y,&z);
        ar[x][y]=z;
        ar[y][x]=z;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(ar[i][j]>(ar[i][k]+ar[k][j])) {
                    ar[i][j]=ar[i][k]+ar[k][j];
                    par[i][j]=par[i][k];
                }
            }
        }
    }
    scanf("%lld",&query);
    while(query--) {
        scanf("%lld %lld",&u,&v);
        if(ar[u][v]==INT_MAX) {
            printf("-1\n");
        } else {
            ll ck=1,wa,ol;
            cnt=0,wa=L;
            path(u,v);
            //cout<<vt.size()<<endl;
            for(int i=0; i<(int)vt.size()-1; i++) {
                ol=ar[vt[i]][vt[i+1]];
                if(wa<ol&&wa==L) {
                    ck=0;
                    break;
                } else if(wa<ol) {
                    wa+=(L-wa);
                    cnt++;
                }
                wa-=(ol);
                if(wa<0) {
                    ck=0;
                    break;
                }
            }
            if(ck==0) {
                printf("-1\n");
            } else {
                printf("%lld\n",cnt);
            }
            vt.clear();
        }
    }
    return 0;
}



Compiler output:
a.cc:88:4: error: redefinition of 'long long int ar [305][305]'
   88 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:4:4: note: 'long long int ar [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:88:17: error: redefinition of 'long long int par [305][305]'
   88 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:4:17: note: 'long long int par [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:89:12: error: redefinition of 'std::vector<int> vt'
   89 | vector<int>vt;
      |            ^~
a.cc:5:12: note: 'std::vector<int> vt' previously declared here
    5 | vector<int>vt;
      |            ^~
a.cc:90:6: error: redefinition of 'void fun(long long int)'
   90 | void fun(ll n) {
      |      ^~~
a.cc:6:6: note: 'void fun(long long int)' previously defined here
    6 | void fun(ll n) {
      |      ^~~
a.cc:102:6: error: redefinition of 'void path(long long int, long long int)'
  102 | void path(ll u,ll v) {
      |      ^~~~
a.cc:18:6: note: 'void path(long long int, long long int)' previously defined here
   18 | void path(ll u,ll v) {
      |      ^~~~
a.cc:111:5: error: redefinition of 'int main()'
  111 | int main() {
      |     ^~~~
a.cc:27:5: note: 'int main()' previously defined here
   27 | int main() {
      |     ^~~~
a.cc:172:4: error: redefinition of 'long long int ar [305][305]'
  172 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:4:4: note: 'long long int ar [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:172:17: error: redefinition of 'long long int par [305][305]'
  172 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:4:17: note: 'long long int par [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:173:12: error: redefinition of 'std::vector<int> vt'
  173 | vector<int>vt;
      |            ^~
a.cc:5:12: note: 'std::vector<int> vt' previously declared here
    5 | vector<int>vt;
      |            ^~
a.cc:174:6: error: redefinition of 'void fun(long long int)'
  174 | void fun(ll n) {
      |      ^~~
a.cc:6:6: note: 'void fun(long long int)' previously defined here
    6 | void fun(ll n) {
      |      ^~~
a.cc:186:6: error: redefinition of 'void path(long long int, long long int)'
  186 | void path(ll u,ll v) {
      |      ^~~~
a.cc:18:6: note: 'void path(long long int, long long int)' previously defined here
   18 | void path(ll u,ll v) {
      |      ^~~~
a.cc:195:5: error: redefinition of 'int main()'
  195 | int main() {
      |     ^~~~
a.cc:27:5: note: 'int main()' previously defined here
   27 | int main() {
      |     ^~~~
a.cc:256:4: error: redefinition of 'long long int ar [305][305]'
  256 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:4:4: note: 'long long int ar [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:256:17: error: redefinition of 'long long int par [305][305]'
  256 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:4:17: note: 'long long int par [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:257:12: error: redefinition of 'std::vector<int> vt'
  257 | vector<int>vt;
      |            ^~
a.cc:5:12: note: 'std::vector<int> vt' previously declared here
    5 | vector<int>vt;
      |            ^~
a.cc:258:6: error: redefinition of 'void fun(long long int)'
  258 | void fun(ll n) {
      |      ^~~
a.cc:6:6: note: 'void fun(long long int)' previously defined here
    6 | void fun(ll n) {
      |      ^~~
a.cc:270:6: error: redefinition of 'void path(long long int, long long int)'
  270 | void path(ll u,ll v) {
      |      ^~~~
a.cc:18:6: note: 'void path(long long int, long long int)' previously defined here
   18 | void path(ll u,ll v) {
      |      ^~~~
a.cc:279:5: error: redefinition of 'int main()'
  279 | int main() {
      |     ^~~~
a.cc:27:5: note: 'int main()' previously defined here
   27 | int main() {
      |     ^~~~
a.cc:340:4: error: redefinition of 'long long int ar [305][305]'
  340 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:4:4: note: 'long long int ar [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:340:17: error: redefinition of 'long long int par [305][305]'
  340 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:4:17: note: 'long long int par [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:341:12: error: redefinition of 'std::vector<int> vt'
  341 | vector<int>vt;
      |            ^~
a.cc:5:12: note: 'std::vector<int> vt' previously declared here
    5 | vector<int>vt;
      |            ^~
a.cc:342:6: error: redefinition of 'void fun(long long int)'
  342 | void fun(ll n) {
      |      ^~~
a.cc:6:6: note: 'void fun(long long int)' previously defined here
    6 | void fun(ll n) {
      |      ^~~
a.cc:354:6: error: redefinition of 'void path(long long int, long long int)'
  354 | void path(ll u,ll v) {
      |      ^~~~
a.cc:18:6: note: 'void path(long long int, long long int)' previously defined here
   18 | void path(ll u,ll v) {
      |      ^~~~
a.cc:363:5: error: redefinition of 'int main()'
  363 | int main() {
      |     ^~~~
a.cc:27:5: note: 'int main()' previously defined here
   27 | int main() {
      |     ^~~~
a.cc:424:4: error: redefinition of 'long long int ar [305][305]'
  424 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:4:4: note: 'long long int ar [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:424:17: error: redefinition of 'long long int par [305][305]'
  424 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:4:17: note: 'long long int par [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:425:12: error: redefinition of 'std::vector<int> vt'
  425 | vector<int>vt;
      |            ^~
a.cc:5:12: note: 'std::vector<int> vt' previously declared here
    5 | vector<int>vt;
      |            ^~
a.cc:426:6: error: redefinition of 'void fun(long long int)'
  426 | void fun(ll n) {
      |      ^~~
a.cc:6:6: note: 'void fun(long long int)' previously defined here
    6 | void fun(ll n) {
      |      ^~~
a.cc:438:6: error: redefinition of 'void path(long long int, long long int)'
  438 | void path(ll u,ll v) {
      |      ^~~~
a.cc:18:6: note: 'void path(long long int, long long int)' previously defined here
   18 | void path(ll u,ll v) {
      |      ^~~~
a.cc:447:5: error: redefinition of 'int main()'
  447 | int main() {
      |     ^~~~
a.cc:27:5: note: 'int main()' previously defined here
   27 | int main() {
      |     ^~~~
a.cc:508:4: error: redefinition of 'long long int ar [305][305]'
  508 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:4:4: note: 'long long int ar [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:508:17: error: redefinition of 'long long int par [305][305]'
  508 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:4:17: note: 'long long int par [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:509:12: error: redefinition of 'std::vector<int> vt'
  509 | vector<int>vt;
      |            ^~
a.cc:5:12: note: 'std::vector<int> vt' previously declared here
    5 | vector<int>vt;
      |            ^~
a.cc:510:6: error: redefinition of 'void fun(long long int)'
  510 | void fun(ll n) {
      |      ^~~
a.cc:6:6: note: 'void fun(long long int)' previously defined here
    6 | void fun(ll n) {
      |      ^~~
a.cc:522:6: error: redefinition of 'void path(long long int, long long int)'
  522 | void path(ll u,ll v) {
      |      ^~~~
a.cc:18:6: note: 'void path(long long int, long long int)' previously defined here
   18 | void path(ll u,ll v) {
      |      ^~~~
a.cc:531:5: error: redefinition of 'int main()'
  531 | int main() {
      |     ^~~~
a.cc:27:5: note: 'int main()' previously defined here
   27 | int main() {
      |     ^~~~
a.cc:592:4: error: redefinition of 'long long int ar [305][305]'
  592 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:4:4: note: 'long long int ar [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:592:17: error: redefinition of 'long long int par [305][305]'
  592 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:4:17: note: 'long long int par [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:593:12: error: redefinition of 'std::vector<int> vt'
  593 | vector<int>vt;
      |            ^~
a.cc:5:12: note: 'std::vector<int> vt' previously declared here
    5 | vector<int>vt;
      |            ^~
a.cc:594:6: error: redefinition of 'void fun(long long int)'
  594 | void fun(ll n) {
      |      ^~~
a.cc:6:6: note: 'void fun(long long int)' previously defined here
    6 | void fun(ll n) {
      |      ^~~
a.cc:606:6: error: redefinition of 'void path(long long int, long long int)'
  606 | void path(ll u,ll v) {
      |      ^~~~
a.cc:18:6: note: 'void path(long long int, long long int)' previously defined here
   18 | void path(ll u,ll v) {
      |      ^~~~
a.cc:615:5: error: redefinition of 'int main()'
  615 | int main() {
      |     ^~~~
a.cc:27:5: note: 'int main()' previously defined here
   27 | int main() {
      |     ^~~~
a.cc:676:4: error: redefinition of 'long long int ar [305][305]'
  676 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:4:4: note: 'long long int ar [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |    ^~
a.cc:676:17: error: redefinition of 'long long int par [305][305]'
  676 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:4:17: note: 'long long int par [305][305]' previously declared here
    4 | ll ar[305][305],par[305][305];
      |                 ^~~
a.cc:677:12: error: redefinition of 'std::vector<int> vt'
  677 | vector<int>vt;
      |            ^~
a