D28 基环树 P2607 [ZJOI2008] 骑士_哔哩哔哩_bilibili
基环树¶
一个图包含n个点n条边，且图中只存在一个环，这样的图被称为基环树（又称环套树）。
基环树比树多了一条边，从而形成了一个环。基环树可以看做以环点为根的一颗颗子树构成。
分三类:
(1)无向树
(2)外向树(每个点只有一条入边)
(3)内向树(每个点只有一条出边)
思路¶
类型1：
1.深搜找环。 2.断环成树，对树深搜计算。
类型2：
先处理树（拓扑排序），最后剩下一个环，特殊处理。
例题 #1 [COCI2010-2011#4] DUGOVI¶
题目描述
在一个小镇上有 \(n\) 位居民，每位居民都**恰好从其他一位**居民那里借了一些钱。
现在到了还债的时间。但问题是每个人都把自己的钱用完了；也就是说任何人都无力偿还债务。这样以来产生了很多冲突。
市长决定解决这个问题。他预想要给一部分居民一些钱，以便于他们用来还债。不过当一部分居民拿到了钱，一系列的连锁反应就开始了。
例如， \(A\) 从市长那里得到了钱。\(A\) 赶忙用这些钱偿还 \(B\) 的债务。\(B\) 也正好偿还 \(C\) 的债务，以此类推。
其中，如果 \(B\) 没有足够的钱来一次还清，那么他会把钱暂时留在自己手里等到钱够了；如果还完债后还有剩余， \(B\) 也会自己留着。（\(B\) 的行为对于任意一个人适用）
另一个例子：如果两个镇上的居民**互欠**对方 \(100\) 美元，那么市长只需要给其中一个人 \(100\) 美元，这两个债务就都解决了。
你需要通过程序来计算出：市长至少要支出多少元给一部分居民才能平息一切债务？
输入格式
输入一行一个整数 \(n\)，表示镇上居民的数量。
接下来的 \(n\) 行，每行两个整数 \(A_i,B_i\)，表示第 \(i\) 个人欠第 \(A_i\) 个人 \(B_i\) 美元。
居民从 \(1\sim n\) 编号。
输出格式
输出一行一个整数，表示市长最少支出的金额。
数据规模与约定¶
对于 \(100\%\) 的数据，保证 \(2\le n\le 2\times 10^5\)，\(1\le A_i\le n\) 且 \(A_i\neq i\)，\(1\le B_i\le 10^4\)。
说明¶
题目译自 COCI2010-2011 CONTEST #4 T5 DUGOVI。
先处理树的部分，按入度拓扑排序。然后剩下的是一个环。我们先累计上环的每一个人的固定代价，即他的债务-他的所有收入。然后我们要寻找一个人作为起点，政府给他全额，让他可以开启连锁反应。注意要减去这个人的固定代价。
数组较多，别搞混了。
// Problem: P6486 [COCI2010-2011#4] DUGOVI
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6486
// Memory Limit: 32 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define itn int
#define ps second
#define pf first
int read(){
int x;
cin>>x;
return x;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=3e6+5;
const ull P=137;
const int INF=1e9+7;
/*
策略
如果是一个环，那么给环上的最大边权即可
如果是一个基环树，那么如果一个人的收入不足还，那么需要给钱。并且还需要一个自动资金，给一个人它需要的所有钱。
注意图可能不联通
*/
int fa[N],ind[N],b[N];
int c[N];
int in[N];
int ans;
queue<int> q;
bitset<N> vis;
signed main(){
int n=rd;
for(int i=1;i<=n;i++){
fa[i]=rd;
ind[fa[i]]++;
c[i]=b[i]=rd;
in[fa[i]]+=b[i];
}
for(int i=1;i<=n;i++){
if(!ind[i])q.push(i);
}
while(q.size()){
int x=q.front();
vis[x]=1;
q.pop();
ans+=c[x];
c[fa[x]]-=b[x];//待还的钱
c[fa[x]]=max(c[fa[x]],0ll);
ind[fa[x]]--;
if(!ind[fa[x]])q.push(fa[x]);
}
// cdbg(ans);
for(int i=1;i<=n;i++){
if(!vis[i]){
int mn=INF;
int cur=i;
do{
vis[cur]=1;
mn=min(mn,c[cur]-max(0ll,b[cur]-in[cur]));//撤销代价
ans+=max(0ll,b[cur]-in[cur]);
cur=fa[cur];
}while(cur!=i);
// cdbg(ans,mn,in[3]);
ans+=mn;
}
}
cout<<ans<<endl;
}
例题 #2 [ZJOI2008] 骑士¶
Z 国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照 \(1\) 至 \(n\) 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
输入格式
第一行包含一个整数 \(n\)，描述骑士团的人数。
接下来 \(n\) 行，每行两个整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
输出格式
应输出一行，包含一个整数，表示你所选出的骑士军团的战斗力。
数据规模与约定
对于 \(30\%\) 的测试数据，满足 \(n \le 10\)；
对于 \(60\%\) 的测试数据，满足 \(n \le 100\)；
对于 \(80\%\) 的测试数据，满足 \(n \le 10 ^4\)。
对于 \(100\%\) 的测试数据，满足 \(1\le n \le 10^6\)，每名骑士的战斗力都是不大于 \(10^6\) 的正整数。
solution
基本环树思想+树形DP
回顾
树形DP（“没有上司的舞会”）
-
不选u，f[u][0] = Σmax(f[v][0], f[v][1])
-
选u, f[u][1] = Σf[v][0] + w[u]
请思考
为什么不会形成某个连通块包含多个环的图呢，而仅仅只有可能有连通块是基环树
因为如果只有n-1条边，那么一定是一棵树（因为每一个点至少有一条出边）。此时再加上一条边，就是应该环了。
code
有向图写法（从u最痛恨的人指向u）
/*////////ACACACACACACAC///////////
Code By Ntsc
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,m,ver[N],ans,idx,vis[N],r1,r2,zd[N],f[N][2];
struct node{
int v,nxt;
}e[N];
int h[N];
void add(int a,int b){
e[++idx]={b,h[a]};
h[a]=idx;
}
void find(int u,int rt){//找环,原理很简单:从rt不断走,如果走回了rt就说明有环
vis[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==rt){
r1=u,r2=v;return ;//任意找环上2个点即可
}
if(vis[v])continue;//剪枝
find(v,rt);
}
}
int dfs(int u,int rt){
f[u][0]=0;f[u][1]=zd[u];
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==rt)continue;//保证是树不走环(因为原图是基环树,有一个环) .因为构建的是单向边树,因此不用担心往fa走,无需判定和记录
dfs(v,rt);//
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
return f[u][0];//因为要在断开的边的2端点u1,u2 各进行一次dfs,因此只返回不选u的最大值,避免 u1,u2同时选
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
int u;
cin>>zd[i]>>u;
add(u,i);
}
for(int i=1;i<=n;i++){
if(!vis[i]){//没有被访问，就进去找环
r1=r2=0;//记录环的2个端点(即将要断开的边的2端点)
find(i,i);//找环
if(r1){
int res1=dfs(r1,r1);//从要断开的边的2端点d其中一个出发
int res2=dfs(r2,r2);
ans+=max(res1,res2);
}
}
}
cout<<ans<<endl;
return 0;
}
无向图写法
/*////////ACACACACACACAC///////////
Code By Ntsc
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+5;
int bk_e[N];
int n,m,ver[N],ans,idx=1,vis[N],r1,r2,zd[N],f[N][2];//idx=1便于寻找双向边
struct node{
int v,nxt;
}e[N];
int h[N];
void add(int a,int b){
e[++idx]={b,h[a]};
h[a]=idx;
}
bool find(int u,int in_e){//找环,原理很简单:如果点v在之前已经被访问过,现在又回到了v,说明有环
vis[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(i==(in_e^1))continue;//如果当前u->v的边恰好是fa->u的反向边,则说明走回头路了
if(!vis[v]){
if(find(v,i))return 1;//没访问过,进行往下走
}else{//如果点v在之前已经被访问过,现在又回到了v,说明有环
r1=u,r2=v;bk_e[i]=bk_e[i^1]=1;return 1;
//bk_e标记这一条边(包括其反向边)是要被断开的边 ,后面在dfs时就不能走
}
}
return 0;
}
int dfs(int u,int in_e){
vis[u]=1;//
f[u][0]=0;f[u][1]=zd[u];
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(i==(in_e^1)||bk_e[i])continue;//保证是树不走环(因为原图是基环树,有一个环) .因为构建的是无向边树,因此需判定和记录入边in_e
dfs(v,i);//
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
return f[u][0];//因为要在断开的边的2端点u1,u2 各进行一次dfs,因此只返回不选u的最大值,避免 u1,u2同时选
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
int u;
cin>>zd[i]>>u;
add(u,i);
add(i,u);
}
for(int i=1;i<=n;i++){
if(!vis[i]){//没有被访问，就进去找环
r1=r2=0;//记录环的2个端点(即将要断开的边的2端点)
find(i,0);//找环
if(r1){
int res1=dfs(r1,0);//从要断开的边的2端点d其中一个出发
int res2=dfs(r2,0);
ans+=max(res1,res2);
}
}
}
cout<<ans<<endl;
return 0;
}
很奇怪是是如果这种写法空间开\(N=1e6+5\)，最后一个点会RE
例题 #3 [IOI2008] Island¶
题目描述
你准备浏览一个公园，该公园由 \(N\) 个岛屿组成，当地管理部门从每个岛屿 \(i\) 出发向另外一个岛屿建了一座长度为 \(L_i\) 的桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言，你更喜欢步行。你希望经过的桥的总长度尽可能长，但受到以下的限制：
-
可以自行挑选一个岛开始游览。
-
任何一个岛都不能游览一次以上。
-
无论任何时间，你都可以由当前所在的岛 \(S\) 去另一个从未到过的岛 \(D\)。从 \(S\) 到 \(D\) 有如下方法：
-
步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
-
渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 \(S\) 走到 \(D\) (当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。
-
注意，你不必游览所有的岛，也可能无法走完所有的桥。
请你编写一个程序，给定 \(N\) 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的长度之和的最大值。
输入格式
第一行包含一个整数 \(N\)，即公园内岛屿的数目。
随后的 \(N\) 行每一行用来表示一个岛。第 \(i\) 行由两个以单空格分隔的整数，表示由岛 \(i\) 筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度 \(L_i\)。你可以假设对于每座桥，其端点总是位于不同的岛上。
输出格式
仅包含一个整数，即可能的最大步行距离。
数据范围：
对于 \(100\%\) 的数据，\(2\leqslant N\leqslant 10^6,1\leqslant L_i\leqslant 10^8\)。
我们发现渡船只用来从一个联通块到另外一个联通块。所以我们不考虑。
那么现在就是要在一个联通块中找到最长路径。这个联通块一定是一棵基环树。那么就是基环树上的最长路径，用树形dp即可。
具体来说是**求基环树的直径**，那么从环上的所有点开始向树的部分跑最长，记为d。答案要么是\(d_i+d_j+dist(i,j)\)，要么是\(d_i+len(环长)-1\)。
最难处理的是第一种情况。我们断环为链，那么就是求\(d_i+d_j+dist(i,j)\)的最大值，满足|i-j|<len
// Problem: P4381 [IOI2008] Island
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4381
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define itn int
#define ps second
#define pf first
int read(){
int x;
cin>>x;
return x;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=1e6+5;
const ull P=137;
const int INF=1e9+7;
/*
策略
*/
struct Node{
int v,w;
int id;
};
vector<Node> e[N];
void add(int a,int b,int c,int id){
e[a].push_back({b,c,id});
e[b].push_back({a,c,id});
}
int cir[N],cnt;
int d[N],d2[N],d1[N];
int s[N],s2[N];
list<int> ls;
int stk[N],top;
bitset<N> vis,inc;
int len;
int ans;
int hav;
void dfs(int x,int id){
if(vis[x]){
if(hav)return ;
int y;
do{
y=stk[top--];
inc[y]=1;
cir[++cnt]=y;
}while(y!=x);
hav=1;
return ;
}
stk[++top]=x;
vis[x]=1;
for(auto v:e[x]){
if(v.id==id)continue;
dfs(v.v,v.id);
}
}
void dfsd(int x,int id){
for(auto v:e[x]){
if(inc[v.v])continue;
if(v.id==id)continue;
dfsd(v.v,v.id);
d[x]=max(d[x],d[v.v]+v.w);
}
}
void dfsl(int x,int rt,int id){
// cdbg(x);
for(auto v:e[x]){
if(inc[v.v]==1&&v.id!=id){
len+=v.w;//环长
d1[v.v]=v.w;//点x在环上的两条临边的长度
d2[x]=v.w;
if(v.v!=rt)s[v.v]=s[x]+v.w,dfsl(v.v,rt,v.id);
break;
}
}
}
void solve(int x){
hav=0;
cnt=0;
top=0;
// inc.reset();
dfs(x,0);//找环
int res=0;
for(int i=1;i<=cnt;i++){
dfsd(cir[i],0);
// cdbg(cir[i],d[cir[i]]);
}
len=0;
dfsl(cir[1],cir[1],0);
// cdbg("Ok",len);
for(int i=1;i<=cnt;i++){
res=max(res,d[cir[i]]+len-min(d1[cir[i]],d2[cir[i]]));
}
for(int i=1;i<=cnt;i++){
d2[i]=d2[i+cnt]=d[cir[i]];
s2[i]=s[cir[i]];
if(i==1)s2[cnt+1]=len;
else s2[i+cnt]=s2[i+cnt-1]+s2[i]-s2[i-1];
}
for(int i=1;i<=cnt*2;i++){
// cdbg(s2[i]);
while(ls.size()&&ls.front()<=i-cnt)ls.pop_front();
if(ls.size())res=max(res,d2[i]+d2[ls.front()]+s2[i]-s2[ls.front()]);
while(ls.size()&&d2[ls.back()]-s2[ls.back()]<=d2[i]-s2[i])ls.pop_back();
ls.push_back(i);
}
ans+=res;
for(int i=1;i<=cnt;i++)inc[cir[i]]=0;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n=rd;
for(int i=1;i<=n;i++){
int a=rd,b=rd;
add(i,a,b,i);
}
for(int i=1;i<=n;i++){
if(!vis[i])solve(i);
}
cout<<ans<<endl;
}
练习 #1 探险队¶
计划派遣一支探险队前往邻近的星系。共有 n 名候选人，编号从 1 到 n，需要从中选出探险队成员。组织者希望尽可能多地选出候选人参加探险。
在候选人中进行了一次调查，每个人可以指出一个他不愿意与之一起参加探险的候选人。对于第 i 个候选人，调查结果是一个整数 ai，表示他不愿意与之一起参加探险的候选人的编号；如果 i 号候选人愿意与任何人一起参加探险，则 ai=−1。
现在，组织者需要决定谁将参加探险队。决定是这样的：如果某个候选人 i 被选中，并且 ai≠−1，那么编号为 ai 的候选人不能被选中。组织者希望选出最多数量的探险队成员。
编写一个程序，根据给定的候选人调查结果，确定可以派遣的最大候选人数。
输入格式
第一行输入包含一个整数 n (1≤n≤3⋅10^5)，表示候选人数。
接下来的 n 行中，每行包含一个整数 ai（ai=−1 或 1≤ai≤n,ai≠i），表示第 i 个候选人的调查结果。
输出格式
输出一个整数，表示可以派遣的最大候选人数。
详细子任务附加限制及分值如下表所示。
| 子任务 | 分值 | 附加限制 | 子任务依赖 |
|---|---|---|---|
| 1 | 19 | n≤20 | |
| 2 | 10 | a1=−1，对于 i>1，ai=i−1 | |
| 3 | 15 | 对于所有 i，ai<i | 2 |
| 4 | 13 | 1≤n≤2000 | 1 |
| 5 | 43 | 1≤n≤3⋅105 | 1,2,3,4 |
注意！这里有一个很容易犯的错误。如果用vector写基环树的最大权独立集，并且用记录两端点的写法，考虑如下数据
6
3
3
2
-1
6
1
可能会把3-2识别为环导致2不被统计。此时要判重边（大常数，不建议），或者用**记录边的编号**的方法！。
// Problem: P6223 [COCI2009 Final Exam#1] PODJELA
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6223
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Challenger: Erica N
// ----
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define itn int
#define ps second
#define mp make_pair
#define pf first
int read(){
int x;
cin>>x;
return x;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=3e5+5;
const ull P=137;
const int INF=1e9+7;
/*
策略
基环树上的最大权独立集
*/
int a[N];
int ans;
struct Node{
int v,id;
};
vector<Node> e[N];
void add(int a,int b,int c){
e[a].push_back({b,c});
e[b].push_back({a,c});
}
int f[N][2];
int ban;
int l,r;
int banid;
void dfs2(int x,int fa){
f[x][1]=f[x][0]=0;
// cdbg(x);
for(auto v:e[x]){
if(v.v==fa)continue;
if(v.v==l)continue;
if(v.id==banid)continue;
dfs2(v.v,x);
f[x][1]+=f[v.v][0];
if(ban!=v.v)f[x][0]+=max(f[v.v][0],f[v.v][1]);
else f[x][0]+=f[v.v][0];
}
f[x][1]++;
}
bitset<N> vis;
bool dfs(int x,int fa){
int f=0;
vis[x]=1;
for(auto v:e[x]){
if(v.v==fa)continue;
if(vis[v.v]){
f=1;
l=x,r=v.v;
banid=v.id;
continue;
}
f|=dfs(v.v,x);
}
return f;
}
void solve(int x){
// cdbg(x);
if(dfs(x,0)){//判环
// l，r是得到的环上的两个点
// cdbg(l,r);
ban=r;
int res=0;
dfs2(l,0);//不选r
res=max(f[l][1],f[l][0]);
ban=0;
dfs2(l,0);//可选r
ans+=max(res,f[l][0]);
}else{
l=r=0;
dfs2(x,0);
ans+=max(f[x][1],f[x][0]);
}
// cdbg(ans);
}
signed main(){
freopen("explore.in","r",stdin);
freopen("explore.out","w",stdout);
int n=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
// if(a[i]==i)assert(0);
if(~a[i])add(i,a[i],i);
}
for(int i=1;i<=n;i++){
if(!vis[i])solve(i);
}
cout<<ans<<endl;
return 0;
}
练习 #2 基环树上lca [POI2012] RAN-Rendezvous¶
给定一棵内向森林，多次给定两个点a和b，求点对(x,y)满足：
1.从a出发走x步和从b出发走y步会到达同一个点
2.在1的基础上如果有多解，那么要求max(x,y)最小
3.在1和2的基础上如果有多解，那么要求min(x,y)最小
4.如果在1、2、3的基础上仍有多解，那么要求x>=y
答案有三种：
-
不在同一个联通块内，无解
-
在同一颗子树内，其lca
-
不在同一颗子树内，那么答案就是两颗子树的根节点的其中之一。注意到环是有向的，所以不能选其它环上的点，更劣。
有点卡常。
// Problem: P3533 [POI2012] RAN-Rendezvous
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3533
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
// #define int long long
#define itn int
#define ps second
#define pf first
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
namespace fastOI{
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
}using namespace fastOI;
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=6e5+5;
const ull P=137;
const int INF=1e9+7;
/*
策略
*/
namespace UNI{
int pa[N];
int find(int x){
if(pa[x]==x)return x;
return pa[x]=find(pa[x]);
}
void join(int a,int b){
int faa=find(a);
int fbb=find(b);
if(faa==fbb)return ;
pa[faa]=fbb;
}
}using namespace UNI;
int stk[N],cir[N];
int cnt;
int inc[N];
int vis[N];
int top;
int bel[N],cel[N];
int hav;
int clen[N];
vector<int> e[N],g[N];
void dfs(int x){
//找环
if(vis[x]){
if(!hav){
int y=0;
do{
y=stk[top--];
cir[++cnt]=y;
inc[y]=1;
}while(y!=x);
hav=1;
}
return ;
}
vis[x]=1;
stk[++top]=x;
for(auto v:e[x]){
dfs(v);
}
}
void add(int a,int b){
e[a].pb(b);
}
void addg(int a,int b){
g[a].pb(b);
}
namespace LCA{
int dep[N];
int fa[22][N];
void dfs2(itn x,int f,int rt){
dep[x]=dep[f]+1;
bel[x]=rt;
for(auto v:g[x]){
if(v==f)continue;
if(inc[v])continue;
fa[0][v]=x;
for(int i=1;i<=20;i++){
fa[i][v]=fa[i-1][fa[i-1][v]];
}
dfs2(v,x,rt);
}
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
for(int i=20;~i;i--){
if(dep[fa[i][a]]>=dep[b])a=fa[i][a];
}
if(a==b)return a;
for(int i=20;~i;i--){
if(fa[i][b]!=fa[i][a]){
a=fa[i][a];
b=fa[i][b];
}
}
return fa[0][a];
}
int getDis(int a,int b){
//one must be anc
return abs(dep[a]-dep[b]);
}
}using namespace LCA;
int s[N];
void dfs3(int x,int rt){
// cdbg(x);
for(auto v:e[x]){
if(inc[v]&&v!=rt){
s[v]=s[x]+1;
dfs3(v,rt);
}
}
}
int getDisC(int a,int b){
if(s[a]<s[b]){
return s[b]-s[a];
}
return clen[cel[a]]-(s[a]-s[b]);
}
inline void print(int a,int b){
write(a);
putchar(' ');
write(b);
puts("");
}
signed main(){
// ios::sync_with_stdio(0);
// cout.tie(0);
int n=rd,m=rd;
for(int i=1;i<=n;i++){
pa[i]=i;
}
for(int i=1;i<=n;i++){
int a=rd;
add(i,a);
addg(a,i);
join(i,a);
}
int tot=0;
for(int i=1;i<=n;i++){
if(!vis[find(i)]){ //!!
tot++;
cnt=0;
hav=0;
dfs(i);
for(int i=1;i<=cnt;i++){
cel[cir[i]]=tot;
dfs2(cir[i],0,cir[i]);
}
dfs3(cir[1],cir[1]);
clen[tot]=cnt;
// cdbg("OK");
}
}
while(m--){
int a=rd,b=rd;
if(find(a)!=find(b)){
puts("-1 -1");
continue;
}
if(bel[a]==bel[b]){
int anc=lca(a,b);
print(getDis(a,anc),getDis(b,anc));
}else{
itn c1=bel[a],c2=bel[b];
int x1=getDis(a,c1),y1=getDis(b,c2)+getDisC(c2,c1);
int x2=getDis(a,c1)+getDisC(c1,c2),y2=getDis(b,c2);
if(max(x1,y1)==max(x2,y2)){
if(min(x1,y1)>min(x2,y2))print(x2,y2);
else if(min(x1,y1)<min(x2,y2))print(x1,y1);
else{
if(x1>=y1)print(x1,y1);
else print(y1,x1);
}
}else{
if(max(x1,y1)>max(x2,y2))print(x2,y2);
else print(x1,y1);
}
}
}
}