Codeforces 931D Peculiar apple-tree

In Arcady's garden there grows a peculiar apple-tree that fruits one time per year. Its peculiarity can be explained in following way: there are n inflorescences, numbered from 1 to n. Inflorescence number 1 is situated near base of tree and any other inflorescence with number i (i > 1) is situated at the top of branch, which bottom is p_i-th inflorescence and p_i < i.

Once tree starts fruiting, there appears exactly one apple in each inflorescence. The same moment as apples appear, they start to roll down along branches to the very base of tree. Each second all apples, except ones in first inflorescence simultaneously roll down one branch closer to tree base, e.g. apple in a-th inflorescence gets to p_a-th inflorescence. Apples that end up in first inflorescence are gathered by Arcady in exactly the same moment. Second peculiarity of this tree is that once two apples are in same inflorescence they annihilate. This happens with each pair of apples, e.g. if there are 5 apples in same inflorescence in same time, only one will not be annihilated and if there are 8 apples, all apples will be annihilated. Thus, there can be no more than one apple in each inflorescence in each moment of time.

Help Arcady with counting number of apples he will be able to collect from first inflorescence during one harvest.

Input

First line of input contains single integer number n (2 ≤ n ≤ 100 000)  — number of inflorescences.

Second line of input contains sequence of n - 1 integer numbers p₂, p₃, ..., p_n (1 ≤ p_i < i), where p_i is number of inflorescence into which the apple from i-th inflorescence rolls down.

Output

Single line of output should contain one integer number: amount of apples that Arcady will be able to collect from first inflorescence during one harvest.

Examples

Input

3
1 1

Output

1

Input

5
1 2 2 2

Output

3

Input

18
1 1 1 4 4 3 2 2 2 10 8 9 9 9 10 10 4

Output

4

Note

In first example Arcady will be able to collect only one apple, initially situated in 1st inflorescence. In next second apples from 2nd and 3rd inflorescences will roll down and annihilate, and Arcady won't be able to collect them.

In the second example Arcady will be able to collect 3 apples. First one is one initially situated in first inflorescence. In a second apple from 2nd inflorescence will roll down to 1st (Arcady will collect it) and apples from 3rd, 4th, 5th inflorescences will roll down to 2nd. Two of them will annihilate and one not annihilated will roll down from 2-nd inflorescence to 1st one in the next second and Arcady will collect it.

题意：给你一颗树，然后每个分支上有一个苹果，如果每个分支上两个苹果落下来，那么这两个苹果就没了，然后问你最后剩下了几个苹果

解题思路：一开始我以为是让你求每一个分支（也就是父亲节点）下面有几个子节点，然后对二取余后传递给上一层父亲节点。当我兴高采烈的把代码敲完后，我这份代码连第三个样例都不能过，然后我就打算再看看题目，由于要上课的原因，然后我就在课上想出了这道题的解法。

当我把题目再仔细看了看，然后把那个第三个样例图画出来后，我就发现了，求得是每一个深度是有奇数个苹果还是偶数个苹果，对二取余。dfs遍历跑一遍，记录每一个深度的苹果树，最后判断求和，然后回来一顿敲，AC了。

附上AC代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int head[maxn],n,num[maxn],tot,m,k,vis[maxn];
struct Node{
	int v,next;
}node[maxn*2];
void add(int u,int v){
	node[tot].v=v;node[tot].next=head[u];
	head[u]=tot++;
}
void dfs(int u,int deep){
	if(deep>k) k=deep;
	num[deep]++;
	if(head[u]==-1) return ;
	for(int i=head[u];~i;i=node[i].next){
		int v=node[i].v;
		if(!vis[v]){
			vis[v]=1;
			dfs(v,deep+1);
		}
	}
}
int main(){
	int i,j;
	tot=0;
	k=0;
	memset(head,-1,sizeof(head));
	memset(num,0,sizeof(num));
	memset(vis,0,sizeof(vis));
	scanf("%d",&n);
	for(i=2;i<=n;i++){
		scanf("%d",&m);
		add(m,i);
	}
	dfs(1,1);
	int ans=0;
	for(i=1;i<=k;i++){
		if(num[i]){
			ans+=num[i]%2;
		}
	}
	printf("%d\n",ans);
	return 0;
}