690F1.md (1648B)
1 Source: https://codeforces.com/problemset/problem/690/F1 2 3 F1. Tree of Life (easy) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Heidi has finally found the mythical Tree of Life – a legendary combinatorial structure which is said to contain a prophecy crucially needed to defeat the undead armies. 22 23 On the surface, the Tree of Life is just a regular undirected tree well-known from computer science. This means that it is a collection of *n* points (called vertices), some of which are connected using *n* - 1 line segments (edges) so that each pair of vertices is connected by a path (a sequence of one or more edges). 24 25 To decipher the prophecy, Heidi needs to perform a number of steps. The first is counting the number of lifelines in the tree – these are paths of length 2, i.e., consisting of two edges. Help her! 26 27 Input 28 29 The first line of the input contains a single integer *n* – the number of vertices in the tree (1 ≤ *n* ≤ 10000). The vertices are labeled with the numbers from 1 to *n*. Then *n* - 1 lines follow, each describing one edge using two space-separated numbers *a* *b* – the labels of the vertices connected by the edge (1 ≤ *a* < *b* ≤ *n*). It is guaranteed that the input represents a tree. 30 31 Output 32 33 Print one integer – the number of lifelines in the tree. 34 35 Examples 36 37 Input 38 39 ``` 40 4 41 1 2 42 1 3 43 1 4 44 ``` 45 46 Output 47 48 ``` 49 3 50 ``` 51 52 Input 53 54 ``` 55 5 56 1 2 57 2 3 58 3 4 59 3 5 60 ``` 61 62 Output 63 64 ``` 65 4 66 ``` 67 68 Note 69 70 In the second sample, there are four lifelines: paths between vertices 1 and 3, 2 and 4, 2 and 5, and 4 and 5.