更新中
//Templates From Extended_Ash/Cooevjnz/JacaJava/Tubbcrafft
//To be continued...
//Suffix Automation
char str[N];
int s[N][26],mx[N],f[N],sz[N];
int last=1,cnt=1,n,v[N],r[N],ans=0;
inline int extend(char c){
int p=last,np=last=++cnt,q,nq;
c-='a'; mx[np]=mx[p]+1; sz[np]=1;
for(;p&&!s[p][c];p=f[p]) s[p][c]=np;
if(!p) return f[np]=1;
q=s[p][c];
if(mx[p]+1==mx[q]) f[np]=q;
else {
nq=++cnt;
mx[nq]=mx[p]+1;
f[nq]=f[q]; f[q]=f[np]=nq;
memcpy(s[nq],s[q],26<<2);
for(;p&&s[p][c]==q;p=f[p]) s[p][c]=nq;
}
}
int build(){
scanf("%d%s",&n,str);
for(int i=0;i<n;++i) extend(str[i]);
for(int i=1;i<=cnt;++i) ++v[mx[i]];
for(int i=1;i<=n;++i) v[i]+=v[i-1];
for(int i=cnt;i;--i) r[v[mx[i]]--]=i;
for(int p,i=cnt;i;--i) sz[f[r[i]]]+=sz[r[i]];
}
//String Hash
#define BASE 27
#define LL long long
char s[N]; LL h[N],bas[N];
LL gH(int l,int r){ return h[r]-h[l-1]*bas[r-l+1]; }
void init_hash(){
for(int i=1;i<=n;++i){
bas[i]=bas[i-1]*BASE;
h[i]=h[i-1]*BASE+s[i]-'a';
}
}
//Suffix Array (using hash)
#define BASE 27
#define LL long long
char s[N]; LL h[N],bas[N]; int sa[N],r[N],H[N];
LL gH(int l,int r){ return h[r]-h[l-1]*bas[r-l+1]; }
void init_hash(){
for(int i=1;i<=n;++i){
bas[i]=bas[i-1]*BASE;
h[i]=h[i-1]*BASE+s[i]-'a';
}
}
inline bool cmp(int x,int y){
int l=-1,r=n-max(x,y);
for(int m;l<r;){
m=l+r+1>>1;
if(gH(x,x+m)==gH(y,y+m)) l=m;
else r=m-1;
}
return s[x]<s[y];
}
void buildSa(){
init_hash();
for(int i=1;i<=n;++i) sa[i]=i;
sort(sa+1,sa+1+n,cmp);
for(int i=1;i<=n;++i) r[sa[i]]=i;
for(int i=1,j,k=0;i<=n;H[r[i++]]=k){
if(k) --k;
if(r[i]>1) for(j=sa[r[i]-1];s[i+k]==s[j+k];++k);
}
}
//KMP & ExtendedKMP
int nt[N];
void KMP(char* s,char* c,int& t,int* ans){
int n=strlen(c+1),m=strlen(s+1);
for(int i=1,j;i<n;++i)
for(j=i;j;)
if(c[j=nt[j]]==c[i]) { nt[i+1]=j+1; break; }
for(int i=0,j=0;i<m;++i){
if(j<n && s[i]==c[j]) ++j;
else while(j) if(c[j=nt[j]]==s[i]){ ++j; break; }
if(j==n) ans[++t]=i-n+1;
}
}
//Trie
//manacher
//Tarjan Algorithm
struct Edge{ int u,v,nt; } G[1000010];
int c=1,h[500010],dfn[500010],clk=0,Col=0;
int n,m,low[500010],col[500010],d[500010];
bool b[1000010];
inline void adj(int x,int y){
G[++c]=(Edge){x,y,h[x]}; h[x]=c;
G[++c]=(Edge){y,x,h[y]}; h[y]=c;
}
void tarjan(int u,int v){
clk++; low[v]=dfn[v]=clk;
for(int w,i=h[v];i;i=G[i].nt)
if((w=G[i].v)!=u){
if(!dfn[w]){
tarjan(v,w);
if(low[w]==dfn[w] || low[w]>dfn[v]){ b[i]=1; b[i^1]=1; }
else low[v]=min(low[v],low[w]);
} else low[v]=min(low[v],dfn[w]);
}
}
void dfs(int x,int u,int Cl){
col[x]=Cl;
for(int v,i=h[x];i;i=G[i].nt)
if((v=G[i].v)!=u&&!b[i]&&!col[v]) dfs(v,x,Cl);
}
int main(){
scanf("%d%d",&n,&m);
for(int x,y,i=0;i<m;++i){
scanf("%d%d",&x,&y);
adj(x,y);
}
tarjan(0,1);
for(int i=1;i<=n;++i)
if(!col[i]) dfs(i,0,++Col);
}
//Dijkstra+Heap
struct Node{ int d,id; } x;
struct Edge{ int v,c,nt; } G[100010];
int h[10010],d[10010];
inline bool gmin(int& a,int b){ return a>b?(a=b)|1:0; }
inline bool operator < (Node a,Node b){ return a.d>b.d; }
void dijk(int s){
priority_queue<Node> q;
d[s]=0; q.push((Node){0,s});
for(int u;!q.empty();){
x=q.top(); q.pop();
if(d[u=x.id]<x.d) continue;
for(int v,i=h[u];i;i=G[i].nt)
if(gmin(d[v=G[i].v],d[u]+G[i].c)) q.push((Node){d[v],v});
}
}
//Floyd
int f[N][N];
void Floyd(int n){
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
//ISAP Maxflow
//mincost maxflow
//Kuskral & Prim
//multiplication Lca
struct Tree{
Edge G[N<<1];
int h[N],d[N],f[18][N],cnt;
inline void adj(int x,int y){
G[++cnt]=(Edge){x,y,h[x]}; h[x]=cnt;
G[++cnt]=(Edge){y,x,h[y]}; h[y]=cnt;
}
void dfs(int x,int p){
d[x]=d[p]+1; f[0][x]=p;
for(int j=1;j<18;++j)
f[j][x]=f[j-1][f[j-1][x]];
for(int v,i=h[x];i;i=G[i].nt)
if((v=G[i].v)!=p) dfs(v,x);
}
void build(){ dfs(1,0); }
void swim(int& x,int d){
for(int i=0;d;++i,d>>=1) if(d&1) x=f[i][x];
}
int gLca(int x,int y){
if(d[x]>d[y]) swap(x,y);
LL x1=0,x2=0;
swim(y,d[y]-d[x]);
if(x==y) return x;
for(int j=17;;){
for(;~j&&f[j][x]==f[j][y];--j);
if(j<0) return f[0][x];
x=f[j][x]; y=f[j][y];
}
}
} T;
//Tree chain partition
struct Edge{ int v,nt; } G[N];
int h[N],d[N],top[N],sz[N],son[N];
int f[N],w[N],v[N<<2],n,m,cnt=0,clk=0;
inline void adj(int x,int y){ G[++cnt]=(Edge){y,h[x]}; h[x]=cnt; }
void dfs(int x){
d[x]=d[f[x]]+1; sz[x]=1;
for(int v,i=h[x];i;i=G[i].nt){
dfs(v=G[i].v);
sz[x]+=sz[v];
if(sz[v]>sz[son[x]]) son[x]=v;
}
}
void dt(int x,int p){
w[x]=++clk; top[x]=p;
if(son[x]) dt(son[x],p);
for(int v,i=h[x];i;i=G[i].nt)
if((v=G[i].v)!=son[x]) dt(v,v);
}
int gLca(int x,int y){
for(;top[x]!=top[y];y=f[top[y]])
if(d[top[x]]>d[top[y]]) swap(x,y);
if(d[x]>d[y]) swap(x,y);
return x;
}
int main(){
scanf("%d%d",&n,&m);
for(int x,i=2;i<=n;++i){
scanf("%d",&x);
adj(x,i); f[i]=x;
}
dfs(1); dt(1,1);
for(int x,y,c;m--;){
scanf("%d%d%d",&x,&y);
gLca(x,y);
}
}
//dfs alignment
//Link cut Tree
//disjoin Set (dsu)
int p[N];
inline void init(){
for(int i=0;i<N;++i) p[i]=i;
}
inline int gFa(int x){ return x==f[x]?x:f[x]=gFa(f[x]); }
//powermod && gcd && extend-gcd
#define L long long
inline L pow(L x,L k,L M,L s=1){
for(;k;x=x*x%M,k>>=1) if(k&1) s=s*x%M;
return s;
}
inline int gcd(int a,int b){
for(int c;b;a=b,b=c) c=a%b;
return a;
}
inline int exgcd(int a,int b,int& x,int& y){
if(b){
int r=exgcd(b,a%b,y,x);
y-=x*(a/b); return r;
} else { x=1; y=0; return a; }
}
//Distratic log
#define L long long
map<L,int> rec;
int dislog(int x,int n,int M){ //x^dislog(x,n)=n(MOD M)
if(x==0) return -1;
if(n%M==1) return 0;
L c=1,mul;
int sq=sqrt(M);
for(;(L)sq*sq<=M;++sq);
for(int i=1;i<=sq;++i){
rec[c]=i;
c=c*x%M;
}
mul=c; c=1;
for(int i=0;i<sq;++i){
L m=(L)n*pow(c,M-2);
if(rec[m]) return (rec[m]+i*sq)%M;
c=c*mul%M;
}
return -1;
}
//Miller Rabin
bool test(int n,int a,int d){
if(n==2 || n==a) return 1;
if(~n&1) return 0;
for(;~d&1;d>>=1);
int t=pow(a,d,n);
for(;(d!=n-1)&&(t!=1)&&(t!=n-1);d<<=1) t=(L)t*t%n;
return (t==n-1)||(d&1);
}
bool miller_rabin(int x){
if(x<2) return 0;
int a[5]={2,3,61,101,10007}; //testing set
for(int i=0;i<5;++i) if(!test(n,a[i],n-1)) return 0;
return 1;
}
//linearity sieve for Prime & miu & phi
int w[N],t; bool vis[N];
int phi[N],miu[N];
void get_prime(int n){
phi[1]=miu[1]=1;
for(int i=2;i<=n;++i){
if(!vis[i]){
w[++t]=i;
phi[i]=i-1;
miu[i]=-1;
}
for(int j=1;j<=t&&i*w[j]<=n;++j){
vis[i*w[j]]=1;
if(i%w[j]==0){
miu[i*w[j]]=0;
phi[i*w[j]]=phi[i]*w[j];
break;
}
miu[i*w[j]]=-miu[i];
phi[i*w[j]]=phi[i]*(w[j]-1);
}
}
}
//Segment Tree
//ZKW segment Tree (Use as Binary search tree)
struct ZKW{
int n,M,s[N<<2];
void init(int N):n(N){
for(M=1;M<=n;M<<=1); --M;
for(int i=M+1;i<=M+n;++i) s[i]=1;
for(int i=M;i;--i) s[i]=s[i<<1]+s[i<<1|1];
}
inline int count(int x){ return s[x+M]; }
inline void insert(int x){ for(x+=M;x;x>>=1) ++s[x]; }
inline void remove(int x){ for(x+=M;x;x>>=1) --s[x]; }
inline int rank(int x,int r=1){ for(x+=M;x;x>>=1) if(x&1) r+=s[x^1]; return r; }
inline int pre(int x){
for(x+=M;x;x>>=1)
if((x&1)&&s[x^1]){
for(--x;x<=M;x=(s[x<<1|1]?x<<1|1:x<<1));
return x-M;
}
return -1;
}
inline int suc(int x){
for(x+=M;x;x>>=1)
if((~x&1)&&s[x^1]){
for(++x;x<=M;x=(s[x<<1]?x<<1:x<<1|1));
return x-M;
}
return -1;
}
inline int kth(int k){
for(int x=1;x<=M;)
if(s[x<<1]>=k) x=x<<1;
else { k-=s[x<<1]; x=x<<1|1; }
return x-M;
}
};
//Segment Tree Merging
//Persistence Segment Tree
//fenwick tree
int s[N],n;
inline void add(int x,int k){ for(;x<=n;x+=x&-x) s[x]+=k; }
inline int sum(int x,int S=0){ for(;x;x&=x-1) S+=s[x]; return s; }
//ST list
int st[20][N],n,val[N],lg[N]={-1};
inline int f(int x,int y){ return; } //f is a function like min or gcd
void init(){
for(int i=1;i<=n;++i) st[0][i]=val[i],lg[i]=lg[i-1]+!(i&(i-1));
for(int i=n;i;--i)
for(int j=1;(i+(1<<j)-1)<=n;++j)
st[j][i]=f(st[j-1][i],st[j-1][i+(1<<j-1)][j-1]);
}
int query(int l,int r){
int k=lg[r-l+1];
return f(st[k][l],st[k][r-(1<<k)+1][k]);
}
//preffix Sum
//Matrix power-mod
struct Mat{
int n,m;
int s[16][16];
Mat(){ memset(s,0,sizeof s); }
void clr(){ memset(s,0,sizeof s); }
void set(int x,int y){ n=x; m=y; }
Mat operator * (const Mat& b){
Mat c; c.set(n,b.m);
for(int i=0;i<n;++i)
for(int j=0;j<b.m;++j)
for(int k=0;k<m;++k)
c.s[i][j]=(c.s[i][j]+(L)s[i][k]*b.s[k][j])%M;
return c;
}
} a,b;
void pow(int k){
for(;k;b=b*b,k>>=1) if(k&1) a=a*b;
}
int main(){
a.set(1,N); b.set(N,N);
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
b.s[i][j]=_________;
pow(n);
}
//Treap
//Splay