#include using namespace std; #define all(a) a.begin(),a.end() #define pb push_back #define sz(a) ((int)a.size()) using ll=long long; using u32=unsigned int; using u64=unsigned long long; using i128=__int128; using u128=unsigned __int128; using f128=__float128; using pii=pair; using pll=pair; template using vc=vector; template using vvc=vc>; template using vvvc=vc>; using vi=vc; using vll=vc; using vvi=vc; using vvll=vc; #define vv(type,name,n,...) \ vector> name(n,vector(__VA_ARGS__)) #define vvv(type,name,n,m,...) \ vector>> name(n,vector>(m,vector(__VA_ARGS__))) template using min_heap=priority_queue,greater>; template using max_heap=priority_queue; // https://trap.jp/post/1224/ #define rep1(n) for(ll i=0; i<(ll)(n); ++i) #define rep2(i,n) for(ll i=0; i<(ll)(n); ++i) #define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i) #define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c)) #define cut4(a,b,c,d,e,...) e #define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define per1(n) for(ll i=((ll)n)-1; i>=0; --i) #define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i) #define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i) #define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c)) #define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__) #define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s))) template constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);} template constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);} template void sort_unique(vector &vec){ sort(vec.begin(),vec.end()); vec.resize(unique(vec.begin(),vec.end())-vec.begin()); } template constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;} template constexpr bool chmax(T &a, const S b){if(a istream& operator >> (istream& i, pair &p){return i >> p.first >> p.second;} template ostream& operator << (ostream& o, const pair &p){return o << p.first << ' ' << p.second;} #ifdef i_am_noob #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) template void _do(vector x){for(auto i: x) cerr << i << ' ';cerr << "\n";} template void _do(set x){for(auto i: x) cerr << i << ' ';cerr << "\n";} template void _do(unordered_set x){for(auto i: x) cerr << i << ' ';cerr << "\n";} template void _do(T && x) {cerr << x << endl;} template void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);} #else #define bug(...) 777771449 #endif template void print(vector x){for(auto i: x) cout << i << ' ';cout << "\n";} template void print(set x){for(auto i: x) cout << i << ' ';cout << "\n";} template void print(unordered_set x){for(auto i: x) cout << i << ' ';cout << "\n";} template void print(T && x) {cout << x << "\n";} template void print(T && x, S&&... y) {cout << x << ' ';print(y...);} template istream& operator >> (istream& i, vector &vec){for(auto &x: vec) i >> x; return i;} vvi read_graph(int n, int m, int base=1){ vvi adj(n); for(int i=0,u,v; i> u >> v,u-=base,v-=base; adj[u].pb(v),adj[v].pb(u); } return adj; } vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);} template pair operator + (const pair &a, const pair &b){return {a.first+b.first,a.second+b.second};} template constexpr T inf=0; template<> constexpr int inf = 0x3f3f3f3f; template<> constexpr ll inf = 0x3f3f3f3f3f3f3f3f; template vector operator += (vector &a, int val){for(auto &i: a) i+=val; return a;} template T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;} #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #include using namespace atcoder; using mint=modint998244353; //using mint=modint1000000007; template struct sparse{ vector val[30]; sparse(){} sparse(vector a){ int n=a.size(); val[0]=a; for(int i=1; n-(1<0; ++i){ val[i].resize(n-(1<=r) return e(); int k=__lg(r-l); return op(val[k][l],val[k][r-(1<;} void ahcorz(){ int n,l,r; cin >> n >> l >> r; vi a(n); cin >> a; rep(n) a[i]--; vi in_cyc(n),cyc_id(n),cyc_pos(n),dep(n),rt(n),tl(n),tr(n); vvi cycs; { rep(n) in_cyc[i]=1; vi cnt(n); rep(n) cnt[a[i]]++; queue q; rep(n) if(!cnt[i]) q.push(i); while(!q.empty()){ int u=q.front(); q.pop(); in_cyc[u]=0,cnt[a[u]]--; if(!cnt[a[u]]) q.push(a[u]); } vi vis(n); rep(n) if(in_cyc[i]&&!vis[i]){ vi cyc; cyc.pb(i),vis[i]=1; for(int j=a[i]; j!=i; j=a[j]) cyc.pb(j),vis[j]=1; rep(j,sz(cyc)) cyc_id[cyc[j]]=sz(cycs),cyc_pos[cyc[j]]=j; cycs.pb(cyc); } vvi adj(n); rep(n) adj[a[i]].pb(i); int _t=-1; auto dfs=[&](auto &self, int u, int _rt) -> void{ tl[u]=++_t; rt[u]=_rt; for(auto v: adj[u]) if(!in_cyc[v]){ dep[v]=dep[u]+1; self(self,v,_rt); } tr[u]=_t; }; rep(n) if(in_cyc[i]) dfs(dfs,i,i); } auto is_anc=[&](int u, int v){ return tl[u]<=tl[v]&&tr[u]>=tr[v]; }; vvi mn(n+1); vc> tree(n+1); for(auto &cyc: cycs){ int m=sz(cyc); if(sz(mn[m])) continue; mn[m].resize(m); rep(m) mn[m][i]=inf; set st; rep(m) st.insert(i); queue q; q.push(0),st.erase(0),mn[m][0]=0; int tmpl=l%m,tmpr=tmpl+(r-l); while(!q.empty()&&!st.empty()){ int u=q.front(); q.pop(); while(1){ if(st.empty()) break; auto it=st.lower_bound(u+tmpl); if(it!=st.end()){ if(*it<=u+tmpr) q.push(*it),mn[m][*it]=mn[m][u]+1,st.erase(it); else break; } else{ it=st.begin(); if(m+(*it)<=u+tmpr) q.push(*it),mn[m][*it]=mn[m][u]+1,st.erase(it); else break; } } } tree[m]=sparse(mn[m]); } int q; cin >> q; while(q--){ int u,v; cin >> u >> v; u--,v--; if(cyc_id[rt[u]]!=cyc_id[rt[v]]){ print(-1); continue; } if(!in_cyc[v]){ if(!is_anc(v,u)){ print(-1); continue; } int mn_dis=dep[u]-dep[v]; int k=iceil(mn_dis,r); if(k*l>mn_dis) print(-1); else print(k); continue; } bug(l,r,cyc_pos[u],cyc_pos[v]); int m=sz(cycs[cyc_id[v]]); int mn_dis=(cyc_pos[v]-cyc_pos[rt[u]]); if(mn_dis<0) mn_dis+=m; mn_dis+=dep[u]; int k=iceil(mn_dis,r); bug(k); if(k*l<=mn_dis){ print(k); continue; } int posl=(cyc_pos[rt[u]]+(k*r-dep[u]))%m; int posr=(cyc_pos[rt[u]]+(k*l-dep[u]))%m; if(k*(r-l)+1>=m){ print(k); continue; } posl=cyc_pos[v]-posl,posr=cyc_pos[v]-posr; if(posl<0) posl+=m; if(posr<0) posr+=m; int res; if(posl<=posr){ res=k+tree[m].query(posl,posr+1); } else{ res=k+min(tree[m].query(0,posr+1),tree[m].query(posl,m)); } if(res>inf/2) print(-1); else print(res); } } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); cout << fixed << setprecision(20); int t=1; //cin >> t; while(t--) ahcorz(); }