Migrated from Lutece 1284 郭大侠与苦恼

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

花开雷霆崖，血染伊吕波。

公元1772年。

郭大侠终于照着天行廖的叮嘱，摆出了阵型，准备带着部队与天行廖相逢于雷霆崖。

但郭大侠实在是没有把握，这个阵型是真的如天行廖所言，所向披靡，于是准备在于天行廖相逢前再确认一遍。

按照天行廖的叮嘱说，这个阵型得满足以下两个要求才能发挥最大威力：

1.这个阵型是一颗树，即n个点，n-1条边，任意两点之间都能互相到达。

2.这个阵型满足好朋友的对数大于n对，好朋友即满足P(u,v)=0，P(u,v)表示从u点到v点的简单路径上点编号的异或和。注意P(u,v)和P(v,u)视作一样，只计数一次。

郭大侠的士兵的的确确摆出了一颗树，但是点数太多了，很难统计好朋友的对数。

这可怎么办？

现在郭大侠找到了你，希望你能帮助憔悴的郭大侠解决这个问题，希望你能够数出这棵树上究竟有多少对好朋友。

Input

第一行n，表示点的数量，(1<=n<=100000)

接下来n-1行，每行两个整数u,v，表示点u与点v之间连有一条边(1<=u,v<=n)

保证是一棵树

Output

输出这棵树上究竟有多少对好朋友。

Samples

17
9 8
9 11
9 13
9 15
9 16
11 10
13 12
15 14
16 17
8 1
1 5
5 4
4 6
6 7
7 2
2 3

18

Note

好朋友一共有(1,3),(1,4),(1,9),(3,6),(3,10),(3,12),(3,14),(3,17),(4,10),(4,12),(4,14),(4,17),(5,7),(7,9),(8,10),(8,12),(8,14)和(8,17)

一共18组好朋友

Resources

2016 UESTC Training for Data Structures