• Драгоценные камни
  GEMS
  
  Балтийская олимпиада по информатике, Тарту, Эстония
  Участники: Дания, Эстония, Финляндия, Германия, Латвия, Литва, Польша, Швеция
  

Описание
Фабрика по изготовлению игрушек из драгоценных камней попросила тебя решить следующую задачу. Дан связный граф, не содержащий циклов, т.е. имеется множество вершин, которые соединены между собой ребрами так, что из каждой вершины можно попасть в любую другую двигаясь по ребрам, но из ребер невозможно составить циклов.

Задание
Фабрика будет изготовлять на основании этих графов ювелирные модели. Вершины изготовляются из драгоценных камне, а ребра из золотых цепочек. При этом требуется, чтобы соседние вершины (две вершины, соединенные одним ребром) были бы изготовлены из разных камней. Для каждого положительного числа p найдется точно один сорт драгоценных камней с ценой p.

Входные данные
Первая строка файла GEMS.IN содержит число вершин графа N (1<=N<=10000). Вершины пронумерованы числами от 1 до N. Следующие N-1 строк описывают ребра, на каждой строке одно ребро. Каждая строчка содержит два числа A и B, разделенные пробелом (1<=A,B<=N; A<>B). Эта пара чисел обозначает ребро, которое соединяет вершины A и B.

Выходные данные
Единственная строка выходного файла GEMS.OUT должна содержать одно целое число - минимальную стоимость камней, требуемых для изготовления ювелирной модели

Например:

GEMS.IN
8
1  2
3  1
1  4
5  6
1  5
5  7
5  8

GEMS.OUT
11