Baltic Olympiad in Informatics  
April 2327, 2003, Tartu, Estonia  
Home About BOI Schedule Teams Tasks Practice First day Barrel Table Second day Test data Results Pictures Technical General info Online contest Contact Printable version 
GemsThe GemToys Company asked you to solve the following problem. You are given a connected acyclic graph, i.e. a set of vertices connected by edges in such a way that from each vertex you can reach all the other vertices by traversing the edges, and it does not contain a loop. The GemToys Company is going to produce jewelry models of such graphs. Vertices will be made of gems and edges will be made of gold string. It is required that adjacent vertices are made of different kinds of gems. For each positive integer p there is exactly one kind of gems with the price p. Your task is to write a program computing the minimal total price of the gems needed to make the model.
Input dataThe first line of the input file GEMS.IN contains one positive integer N (1 ≤ N ≤ 10 000), the number of vertices. The vertices are numbered from 1 to N. The following N1 lines describe the edges, one per line. Each of these lines contains a pair of integers A and B separated by a space (1 ≤ A, B ≤ N, A ≠ B). Such a pair represents an edge connecting vertices A and B.
Output dataThe first and only line of the output file GEMS.OUT must contain one integer: the minimal total price of the gems needed to make the model. Sample
