Logic

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 color, so they decided to arrange themselves so that each logician sees exactly one other person with blue eyes. As it ususally happens to be, none of the logicians can see their own eye color, 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?

Input

The first line contains the integer $n(3\le n\le 10^5)$ — 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

If the required arrangement does not exist, in the first and only line output $-1$. Otherwise, print the required least number of blue-eyed logicians.

Examples