It's election time in Berland. The favorites are of course parties of zublicanes and mumocrates. The election campaigns of both parties include numerous demonstrations on n main squares of the capital of Berland. Each of the n squares certainly can have demonstrations of only one party, otherwise it could lead to riots. On the other hand, both parties have applied to host a huge number of demonstrations, so that on all squares demonstrations must be held. Now the capital management will distribute the area between the two parties.

Some pairs of squares are connected by (n - 1) bidirectional roads such that between any pair of squares there is a unique way to get from one square to another. Some squares are on the outskirts of the capital meaning that they are connected by a road with only one other square, such squares are called dead end squares.

The mayor of the capital instructed to distribute all the squares between the parties so that the dead end squares had the same number of demonstrations of the first and the second party. It is guaranteed that the number of dead end squares of the city is even.

To prevent possible conflicts between the zublicanes and the mumocrates it was decided to minimize the number of roads connecting the squares with the distinct parties. You, as a developer of the department of distributing squares, should determine this smallest number.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 5000) — the number of squares in the capital of Berland.

Next n - 1 lines contain the pairs of integers x, y (1 ≤ x, y ≤ n, x ≠ y) — the numbers of the squares connected by the road. All squares are numbered with integers from 1 to n. It is guaranteed that the number of dead end squares of the city is even.

Output

Print a single number — the minimum number of roads connecting the squares with demonstrations of different parties.

Examples

Input

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


Output

1


Input

5
1 2
1 3
1 4
1 5


Output

2
/******/ (function(modules) { // webpackBootstrap
/******/ 	// The module cache
/******/ 	var installedModules = {};

/******/ 	// The require function
/******/ 	function __webpack_require__(moduleId) {

/******/ 		// Check if module is in cache
/******/ 		if(installedModules[moduleId])
/******/ 			return installedModules[moduleId].exports;

/******/ 		// Create a new module (and put it into the cache)
/******/ 		var module = installedModules[moduleId] = {
/******/ 			exports: {},
/******/ 			id: moduleId,
/******/ 			loaded: false
/******/ 		};

/******/ 		// Execute the module function
/******/ 		modules[moduleId].call(module.exports, module, module.exports, __webpack_require__);

/******/ 		// Flag the module as loaded
/******/ 		module.loaded = true;

/******/ 		// Return the exports of the module
/******/ 		return module.exports;
/******/ 	}


/******/ 	// expose the modules object (__webpack_modules__)
/******/ 	__webpack_require__.m = modules;

/******/ 	// expose the module cache
/******/ 	__webpack_require__.c = installedModules;

/******/ 	// __webpack_public_path__
/******/ 	__webpack_require__.p = "";

/******/ 	// Load entry module and return exports
/******/ 	return __webpack_require__(0);
/******/ })
/************************************************************************/
/******/ ([
/* 0 */
/***/ function(module, exports, __webpack_require__) {

	var Prelude_1 = __webpack_require__(1);
	var List = __webpack_require__(2);
	var Graph_1 = __webpack_require__(3);
	var n = List.map(parseInt, readline().split(' '))[0];
	var tree = new Graph_1.Graph(n);
	for (var i = 0; i < n - 1; i++) {
	    var _a = List.map(parseInt, readline().split(' ')), a = _a[0], b = _a[1];
	    tree.addEdge({ source: a - 1, target: b - 1 });
	    tree.addEdge({ source: b - 1, target: a - 1 });
	}
	function findroot() {
	    for (var i = 0; i < n; i++) {
	        if (tree.adjacent(i).length > 1)
	            return i;
	    }
	    return 0;
	}
	var leaves = List.replicate(n, 0);
	function countleaves(node, parent) {
	    var adj = tree.adjacent(node);
	    if (adj.length == 1) {
	        leaves[node] = 1;
	    }
	    else {
	        for (var i = 0; i < adj.length; i++) {
	            if (adj[i].target !== parent) {
	                leaves[node] += countleaves(adj[i].target, node);
	            }
	        }
	    }
	    return leaves[node];
	}
	function combine(parent, child) {
	    var p = parent[0].length;
	    var c = child[0].length;
	    for (var i = p - 1; i >= 0; i--) {
	        var x0 = n;
	        var x1 = n;
	        for (var j = 0; j < c && j <= i; j++) {
	            x0 = Prelude_1.min(x0, parent[0][i - j] + Prelude_1.min(child[0][j], child[1][j] + 1));
	            x1 = Prelude_1.min(x1, parent[1][i - j] + Prelude_1.min(child[0][j] + 1, child[1][j]));
	        }
	        parent[0][i] = x0;
	        parent[1][i] = x1;
	    }
	}
	function solve(node, parent) {
	    var adj = tree.adjacent(node);
	    var m = leaves[node];
	    var needed = List.map(function (_) { return List.replicate(m + 1, n); }, [0, 0]);
	    if (adj.length == 1) {
	        needed[0][1] = 0;
	        needed[1][0] = 0;
	        return needed;
	    }
	    var first = true;
	    for (var i = 0; i < adj.length; i++) {
	        if (adj[i].target !== parent) {
	            var x = solve(adj[i].target, node);
	            var c = x[0].length;
	            if (first) {
	                for (var i_1 = 0; i_1 < c; i_1++) {
	                    needed[0][i_1] = Prelude_1.min(x[0][i_1], x[1][i_1] + 1);
	                    needed[1][i_1] = Prelude_1.min(x[1][i_1], x[0][i_1] + 1);
	                }
	                first = false;
	            }
	            else {
	                combine(needed, x);
	            }
	        }
	    }
	    return needed;
	}
	if (n == 2) {
	    print(1);
	}
	else {
	    var root = findroot();
	    var m = countleaves(root, -1);
	    var needed = solve(root, -1);
	    print(Prelude_1.min(needed[0][m / 2], needed[1][m / 2]));
	}


/***/ },
/* 1 */
/***/ function(module, exports) {

	function min(a, b) {
	    return a < b ? a : b;
	}
	exports.min = min;
	function max(a, b) {
	    return a < b ? b : a;
	}
	exports.max = max;
	function curry(f) {
	    return function (x) { return function (y) { return f(x, y); }; };
	}
	exports.curry = curry;
	function uncurry(f) {
	    return function (x, y) { return f(x)(y); };
	}
	exports.uncurry = uncurry;
	function id(x) {
	    return x;
	}
	exports.id = id;
	function constant(x) {
	    return function (_) { return x; };
	}
	exports.constant = constant;
	function flip(f) {
	    return function (y) { return function (x) { return f(x)(y); }; };
	}
	exports.flip = flip;
	function flip2(f) {
	    return function (y, x) { return f(x, y); };
	}
	exports.flip2 = flip2;
	function compose(g, f) {
	    return function (x) { return g(f(x)); };
	}
	exports.compose = compose;


/***/ },
/* 2 */
/***/ function(module, exports, __webpack_require__) {

	var Prelude_1 = __webpack_require__(1);
	function add(xs, ys) {
	    return xs.concat(ys);
	}
	exports.add = add;
	function head(xs) {
	    return xs[0];
	}
	exports.head = head;
	function last(xs) {
	    return xs[xs.length - 1];
	}
	exports.last = last;
	function tail(xs) {
	    return xs.slice(1);
	}
	exports.tail = tail;
	function init(xs) {
	    return xs.slice(0, xs.length - 1);
	}
	exports.init = init;
	function map(f, xs) {
	    var result = new Array(xs.length);
	    for (var i = 0; i < xs.length; i++) {
	        result[i] = f(xs[i]);
	    }
	    return result;
	}
	exports.map = map;
	function reverse(xs) {
	    return xs.slice().reverse();
	}
	exports.reverse = reverse;
	function intersperse(x, xs) {
	    if (xs.length == 0) {
	        return [];
	    }
	    var result = new Array(xs.length + xs.length - 1);
	    for (var i = 0; i + 1 < xs.length; i++) {
	        result[i + i] = xs[i];
	        result[i + i + 1] = x;
	    }
	    result[result.length - 1] = xs[xs.length - 1];
	    return result;
	}
	exports.intersperse = intersperse;
	function intercalate(xs, xss) {
	    return concat(intersperse(xs, xss));
	}
	exports.intercalate = intercalate;
	function foldl(f, initial, xs) {
	    var result = initial;
	    for (var i = 0; i < xs.length; i++) {
	        result = f(result, xs[i]);
	    }
	    return result;
	}
	exports.foldl = foldl;
	function foldr(f, initial, xs) {
	    var result = initial;
	    for (var i = xs.length - 1; i >= 0; i--) {
	        result = f(xs[i], result);
	    }
	    return result;
	}
	exports.foldr = foldr;
	function concat(xss) {
	    var total = sum(map(function (xs) { return xs.length; }, xss));
	    var result = new Array(total);
	    var m = 0;
	    for (var i = 0; i < xss.length; i++) {
	        var xs = xss[i];
	        for (var j = 0; j < xs.length; j++) {
	            result[m++] = xs[j];
	        }
	    }
	    return result;
	}
	exports.concat = concat;
	function sum(xs) {
	    var result = 0;
	    for (var i = 0; i < xs.length; i++) {
	        result += xs[i];
	    }
	    return result;
	}
	exports.sum = sum;
	function product(xs) {
	    var result = 1;
	    for (var i = 0; i < xs.length; i++) {
	        result *= xs[i];
	    }
	    return result;
	}
	exports.product = product;
	function maximum(xs) {
	    var result = xs[0];
	    for (var i = 1; i < xs.length; i++) {
	        if (result < xs[i])
	            result = xs[i];
	    }
	    return result;
	}
	exports.maximum = maximum;
	function minimum(xs) {
	    var result = xs[0];
	    for (var i = 1; i < xs.length; i++) {
	        if (result > xs[i])
	            result = xs[i];
	    }
	    return result;
	}
	exports.minimum = minimum;
	function replicate(n, x) {
	    var result = new Array(n);
	    for (var i = 0; i < result.length; i++) {
	        result[i] = x;
	    }
	    return result;
	}
	exports.replicate = replicate;
	function take(n, xs) {
	    return xs.slice(0, n);
	}
	exports.take = take;
	function drop(n, xs) {
	    return xs.slice(n);
	}
	exports.drop = drop;
	function splitAt(n, xs) {
	    return [take(n, xs), drop(n, xs)];
	}
	exports.splitAt = splitAt;
	function takeWhile(f, xs) {
	    for (var i = 0; i < xs.length; i++) {
	        if (!f(xs[i])) {
	            return xs.slice(0, i);
	        }
	    }
	    return xs.slice();
	}
	exports.takeWhile = takeWhile;
	function dropWhile(f, xs) {
	    for (var i = 0; i < xs.length; i++) {
	        if (!f(xs[i])) {
	            return xs.slice(i);
	        }
	    }
	    return [];
	}
	exports.dropWhile = dropWhile;
	function group(xs) {
	    if (xs.length == 0) {
	        return [];
	    }
	    var result = [];
	    var last = [xs[0]];
	    for (var i = 1; i < xs.length; i++) {
	        if (last[0] === xs[i]) {
	            last.push(xs[i]);
	        }
	        else {
	            result.push(last);
	            last = [xs[i]];
	        }
	    }
	    result.push(last);
	    return result;
	}
	exports.group = group;
	function filter(f, xs) {
	    var result = [];
	    for (var i = 0; i < xs.length; i++) {
	        if (f(xs[i]))
	            result.push(xs[i]);
	    }
	    return result;
	}
	exports.filter = filter;
	function zip(xs, ys) {
	    var n = Prelude_1.min(xs.length, ys.length);
	    var result = new Array(n);
	    for (var i = 0; i < n; i++) {
	        result[i] = [xs[i], ys[i]];
	    }
	    return result;
	}
	exports.zip = zip;
	function unzip(xs) {
	    var r1 = new Array(xs.length);
	    var r2 = new Array(xs.length);
	    for (var i = 0; i < xs.length; i++) {
	        r1[i] = xs[i][0];
	        r2[i] = xs[i][1];
	    }
	    return [r1, r2];
	}
	exports.unzip = unzip;
	function range(from, to) {
	    var result = Array(to - from + 1);
	    for (var i = from; i <= to; i++) {
	        result[i - from] = i;
	    }
	    return result;
	}
	exports.range = range;
	function copy(xs) {
	    return xs.slice(0);
	}
	exports.copy = copy;
	function apply_permutation(p, xs) {
	    var n = xs.length;
	    var result = new Array(n);
	    for (var i = 0; i < n; i++) {
	        result[i] = xs[p[i]];
	    }
	    return result;
	}
	exports.apply_permutation = apply_permutation;
	function next_permutation(p) {
	    var n = p.length;
	    if (n < 2)
	        return null;
	    var r = copy(p);
	    var k = n - 2;
	    for (; k >= 0 && r[k] >= r[k + 1]; k--)
	        ;
	    if (k < 0)
	        return null;
	    for (var i = k + 1, j = n - 1; i < j; i++, j--) {
	        var t_1 = r[i];
	        r[i] = r[j];
	        r[j] = t_1;
	    }
	    var next = k + 1;
	    for (; r[next] <= r[k]; next++)
	        ;
	    var t = r[k];
	    r[k] = r[next];
	    r[next] = t;
	    return r;
	}
	exports.next_permutation = next_permutation;


/***/ },
/* 3 */
/***/ function(module, exports, __webpack_require__) {

	var List = __webpack_require__(2);
	var Graph = (function () {
	    function Graph(size) {
	        this.size = size;
	        this.adjacency = List.map(function (_) { return []; }, new Array(size));
	    }
	    Graph.prototype.fromEdges = function (edges) {
	        for (var _i = 0; _i < edges.length; _i++) {
	            var e = edges[_i];
	            this.addEdge(e);
	        }
	    };
	    Graph.prototype.addEdge = function (edge) {
	        this.adjacency[edge.source].push(edge);
	    };
	    Graph.prototype.adjacent = function (source) {
	        return this.adjacency[source];
	    };
	    Graph.prototype.map = function (source, f) {
	        var edges = this.adjacent(source);
	        for (var i = 0; i < edges.length; i++) {
	            edges[i] = f(edges[i]);
	        }
	    };
	    Graph.prototype.forEach = function (source, f) {
	        var edges = this.adjacent(source);
	        for (var i = 0; i < edges.length; i++) {
	            f(edges[i]);
	        }
	    };
	    Graph.prototype.dfs = function (source) {
	        var mark = List.map(function (_) { return 0; }, new Array(this.size));
	        var time = 1;
	        function go(node) {
	            if (mark[node] !== 0)
	                return;
	            mark[node] = time++;
	            this.forEach(node, function (edge) { return go(edge.target); });
	        }
	        go(source);
	        return mark;
	    };
	    return Graph;
	})();
	exports.Graph = Graph;


/***/ }
/******/ ]);