背景

题目描述

机器猫想要让集训队成员之间的关系变得更好，于是他从百宝袋中拿出了丘比特之箭。

集训队成员之间的人际关系网可以看成是一张有 $n$ 个点 $n$ 条边的无向简单连通图。

机器猫可以给一位集训队成员分发一只丘比特之弓，他会向所有他认识的成员射出丘比特之箭。

每个成员只能向他认识的成员射箭，也不能给自己射箭。

每个成员只能被一只丘比特之箭射中，否则后果不堪设想。

请你帮机器猫算出最少需要多少丘比特之弓才能使每个成员都被丘比特之箭射中，或者报告无解。

输入

第一行有一个整数 $n\ (3\le n \le 10^5)$，表示成员的总数和关系边数。

接下来的 $n$ 行每行有两个整数 $u_i,v_i$ ，表示一条成员关系，保证成员关系构成一张无向简单连通图。

输出

输出一行一个整数，表示菜猫需要的最少的丘比特之弓数目；或者报告无解，即输出 -1。

样例

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

4

仅有一种合法方案：给成员 $1,2,6,7$ 分发丘比特之弓。

3
1 2
2 3
3 1

-1

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

8

来源

2025 UESTC ICPC Training for Dynamic Programming and Search