还记得那两只喜欢吃木板的白蚁吗？它们对脑力锻炼从不感到厌倦。在吃掉了 Byteland 的大部分栅栏后，它们现在对树产生了兴趣。

树是一个具有 $n$ 个顶点和 $n-1$ 条边的连通无向图。这两只白蚁很快就对单调地吃掉顶点感到厌倦了——为了让进食更有趣，它们发明了一个游戏。它们约定了一个树的边序 $(e_{1}, e_{2}, ..., e_{n-1})$。游戏最多持续 $n-1$ 轮，每一轮恰好有一只白蚁进行操作。玩家轮流行动（先手在第 1 轮行动，后手在第 2 轮，第 3 轮又是先手，以此类推）。在第 $k$ 轮中，行动的白蚁必须选择边 $e_{k}$ 的一个尚未被吃掉的端点并将其吃掉。如果边 $e_{k}$ 的两个端点在白蚁行动前都已经被吃掉，则游戏结束，该白蚁输掉比赛。如果游戏在 $n-1$ 轮后仍未结束，则为平局。

我们假设白蚁（毕竟是这类游戏的老手）会进行无误的操作，拥有获胜策略的白蚁希望在尽可能早的轮次获胜，而它的对手则试图尽可能推迟失败。你的任务是对于给定的树和白蚁设定的边序，确定游戏结束的轮次。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 500\,000$)，表示树的顶点数。接下来的 $n-1$ 行给出了白蚁设定的树的边序。其中第 $i$ 行包含两个整数 $u_{i}$ 和 $v_{i}$ ($1 \le u_{i}, v_{i} \le n$)，表示边 $e_{i}$ 的两个端点的编号。

输出格式

在第一行输出一个整数，表示游戏结束的轮次；如果游戏以平局结束，则输出 -1。

样例

输入 1

5
2 3
1 2
4 5
3 4

输出 1

4

说明

如果在第一轮中，先手白蚁吃掉了顶点 3，并且在第三轮中它吃掉了顶点 4，那么无论对手在第二轮如何操作，它在第四轮都将没有合法的移动空间。