The second semester starts at the University of Pavlopolis. After vacation in Vičkopolis Noora needs to return to Pavlopolis and continue her study. Sometimes (or quite often) there are teachers who do not like you. Incidentally Noora also has one such teacher. His name is Yury Dmitrievich and he teaches graph theory. Yury Dmitrievich doesn't like Noora, so he always gives the girl the most difficult tasks. So it happened this time. The teacher gives Noora a tree with n vertices. Vertices are numbered with integers from 1 to n . The length of all the edges of this tree is 1 . Noora chooses a set of simple paths that pairwise don't intersect in edges. However each vertex should belong to at least one of the selected path. For each of the selected paths, the following is done: We choose exactly one edge ( u , v ) that belongs to the path. On the selected edge ( u , v ) there is a point at some selected distance x from the vertex u and at distance 1 - x from vertex v . But the distance x chosen by Noora arbitrarily, i. e. it can be different for different edges. One of the vertices u or v is selected. The point will start moving to the selected vertex. Let us explain how the point moves by example. Suppose that the path consists of two edges ( v 1 , v 2 ) and ( v 2 , v 3 ) , the point initially stands on the edge ( v 1 , v 2 ) and begins its movement to the vertex v 1 . Then the point will reach v 1 , then "turn around", because the end of the path was reached, further it will move in another direction to vertex v 2 , then to vertex v 3 , then "turn around" again, then move to v 2 and so on. The speed of the points is 1 edge per second. For example, for 0.5 second the point moves to the length of the half of an edge. A stopwatch is placed at each vertex of the tree. The time that the stopwatches indicate at start time is 0 seconds. Then at the starting moment of time, all points simultaneously start moving from the selected positions to selected directions al