A group of perfect logicians has again received a request to be the main protagonists of a new logic puzzle. They must now agree upon which $n$ of them should participate.

This time the logic puzzle takes place on an undirected graph with $n$ nodes, and logically, $n$ edges. Each edge connects two different nodes and between any two nodes there is at most one edge. Additionally, the graph is connected, which means that it is possible to go from any node to any other node via a sequence of edges. For each node there will be one logician located on that node and each logician is able to see precisely those logicians whose nodes are connected by an edge with their own node.

They already suspected that the catch might be related to their eye colour, so they decided to arrange themselves so that each logician sees exactly one other person with blue eyes. As it usually happens to be, none of the logicians can see their own eye colour, which means that even logicians with blue eyes should see exactly one other person with blue eyes.

What is the least number of blue-eyed logicians needed to make the required arrangement?

Constraints

In every subtask, it holds that $3\le n\le 100000$.

Subtask	Points	Constraints
1	10	Each logician sees exactly two other logicians.
2	10	$3\le n\le 20$
3	40	$3\le n\le 1000$
4	50	No additional constraints.

Input Specification

The first line contains the integer $n$, the number of nodes in the graph, and also the number of logicians.

The following $n$ lines contain pairs of integers representing the edges of the graph. Each edge connects two different nodes and no edge is repeated twice in the input.

Output Specification

If the required arrangement does not exist, in the first and only line output -1.

Otherwise, in the first and only line output the required least number of blue-eyed logicians.

Sample Input 1

4
1 2
2 3
3 4
4 1

Sample Output 1

2

Explanation for Sample Output 1

Blue-eyed logicians could for example be those on nodes $1$ and $2$.

Sample Input 2

3
1 2
2 3
3 1

Sample Output 2

-1

Explanation for Sample Output 2

If only one of the logicians has blue eyes, then he surely can't see anyone else with blue eyes. If there are two or more of them with blue eyes, then surely someone will see more than one person with blue eyes.

Sample Input 3

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

Sample Output 3

4