一群完美的逻辑学家再次接到请求，成为一个新逻辑谜题的主角。他们现在必须商定由其中的 $n$ 个人参与。

这次逻辑谜题发生在一个包含 $n$ 个节点和 $n$ 条边的无向图上。每条边连接两个不同的节点，且任意两个节点之间最多只有一条边。此外，该图是连通的，这意味着可以通过一系列边从任意节点到达其他任何节点。每个节点上都有一位逻辑学家，每位逻辑学家都能准确地看到那些与自己所在节点有边相连的逻辑学家。

他们已经怀疑谜题的玄机可能与眼睛颜色有关，因此他们决定进行排列，使得每位逻辑学家都能恰好看到一位蓝眼睛的人。正如通常发生的那样，逻辑学家无法看到自己的眼睛颜色，这意味着即使是蓝眼睛的逻辑学家，也应该恰好看到一位蓝眼睛的人。

为了达成所需的排列，最少需要多少名蓝眼睛的逻辑学家？

输入格式

第一行包含整数 $n$，表示图中的节点数，也是逻辑学家的数量。 接下来的 $n$ 行包含表示图的边的整数对。每条边连接两个不同的节点，且输入中不会重复出现同一条边。

输出格式

如果所需的排列不存在，则在第一行输出 -1。 否则，在第一行输出所需的蓝眼睛逻辑学家的最少数量。

子任务

在每个子任务中，均满足 $3 \le n \le 100\,000$。

样例

输入格式 1

4
1 2
2 3
3 4
4 1

输出格式 1

2

说明

蓝眼睛的逻辑学家可以是节点 1 和节点 2 上的那些人。

输入格式 2

3
1 2
2 3
3 1

输出格式 2

-1

说明

如果只有一名逻辑学家是蓝眼睛，那么他肯定看不到其他蓝眼睛的人。如果有两名或更多蓝眼睛的人，那么肯定会有人看到不止一名蓝眼睛的人。

输入格式 3

7
1 2
2 3
3 4
4 5
5 6
6 7
2 4

输出格式 3

4