prufer 序列完成了从一棵大小为 \(n\) 的无根树到长度为 \(n-2\) 的序列的双射，下面简述其构造过程：

从一棵无根树到 prufer 序列：

我们找到其编号最小的叶子，然后删掉叶子，把其父亲加入队列。重复操作，直到整棵树剩下两个节点。

\(O(n\log n)\) 是显然可以做的，我们考虑如何 \(O(n)\)。

用一个指针，指向当前编号最小的叶子节点，然后删掉他，如果其父亲变成了叶子，并且编号比它小，我们就删掉其父亲并重复操作，否则我们往后推指针，找到下一个叶子。

从 prufer 序列到一棵无根树

容易发现，每个节点的度数是在 prufer 序列中的出现次数加 \(1\)，考虑我们现在知道每个点的度数，然后我们找到编号最小的叶子，然后删掉它，如果其父亲也变成了叶子，并且编号较小，我们重复这个操作，否则的话，我们考虑往后推指针，找到下一个叶子。最后会剩下两个点，其中一个节点是 \(n\)，我们只需要在 prufer 序列最后加入 \(n\) 就可以避免特判。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define int long long
#define ull unsigned long long
#define mset(a,b) memset(a,b,sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define N 5000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,m,d[N];

namespace Subtask1{

    int k=INF,fa[N],p[N];

    inline void Solve(){
        for(int i=1;i<=n-1;i++){
            int x;read(x);
            d[x]++;d[i]++;fa[i]=x;
        }
        for(int i=1,j=1;i<=n-2;i++,j++){
            while(d[j]!=1) j++;p[i]=fa[j];d[j]--;d[fa[j]]--;
            while(i<=n-2&&d[p[i]]==1&&p[i]<j){p[i+1]=fa[p[i]];d[p[i]]--;d[fa[p[i]]]--;i++;}
        }
        int ans=0;
        for(int i=1;i<=n-2;i++) ans=(ans^(i*p[i]));
        printf("%lld\n",ans);
    }
}

namespace Subtask2{

    int fa[N],p[N],d[N];

    inline void Solve(){
        for(int i=1;i<=n-2;i++) read(p[i]),d[p[i]]++;
        p[n-1]=n;
        for(int i=1;i<=n;i++) d[i]++;
        for(int i=1,j=1;i<=n-1;i++,j++){
            while(d[j]!=1) j++;fa[j]=p[i];d[j]--;d[p[i]]--;
            while(i<=n-1&&d[p[i]]==1&&p[i]<j){fa[p[i]]=p[i+1];d[p[i]]--;d[fa[p[i]]]--;i++;}
        }
        int ans=0;
        for(int i=1;i<=n-1;i++) ans=(ans^(i*fa[i]));
        printf("%lld\n",ans);
    }
}

signed main(){
    read(n);read(m);
    if(m==1) Subtask1::Solve();else Subtask2::Solve();
    return 0;
}