题目描述

图 $G$ 上有 $n$ 个点，依次从 $1$ 到 $n$ 编号，初始图上没有边，将有 $n-1$ 次操作来添加长度均为 $1$ 的边，保证图时刻是一个森林（每个连通块都分别构成树），每次加边后你需要计算森林中每棵树的直径长度之和。

直径长度定义为树中最远的两个点之间的距离，距离定义为最短路径上的边权和。一个点的树的直径长度是 $0$。

为了保证你真的在即时处理询问，而不是把它们存下来之后慢慢处理，你需要维护一个初值为 $0$ 的变量 $var$，每次加边给定 $a,b$，你需要计算 $u=a\operatorname{xor}var,v=b\operatorname{xor}var$，并在 $u,v$ 之间加边，保证 $1\leq u,v\leq n$，加边之后记当前每棵树的直径长度之和为 $d$，令 $var = d \operatorname{xor} var$。

你只需要输出最后的 $var$ 的值。

输入格式

第一行两个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $a,b$，含义见题目描述。

输出格式

输出一行一个整数，表示最后的 $var$ 的值。

3 
1 2
3 2

3

样例解释 1

第一次加边后森林的直径之和是 0+1=1， 第二次实际加的边是 u=2,v=3， 加边后森林的直径之和是 2， 输出 1 xor 2 =3。

数据范围

对于 $30\%$ 的数据，$1\leq n\leq 100$。

对于 $60\%$ 的数据，$1\leq n\leq 3000$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$0\leq a,b\leq 2n$，$1\leq u,v\leq n$。