{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\r\nThe Chef is enjoying a wonderful vacation in Byteland. What makes the Chef impressed the most is the road system of the country. Byteland has \u003cb\u003eN\u003c/b\u003e cities numbered 1 through \u003cb\u003eN\u003c/b\u003e. City 1 is the capital of Byteland. The country also has \u003cb\u003eN\u003c/b\u003e-1 bidirectional roads connecting the cities. The \u003cb\u003ei\u003c/b\u003e-th road connects two different cities \u003cb\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. In this road system, people can travel between every pair of different cities by going through exactly one path of roads.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nThe roads are arranged in such a way that people can distinguish two cities only when both cities have different number of roads connected to it. Such two cities will be considered \u003ci\u003esimilar\u003c/i\u003e. For example, city \u003cb\u003eA\u003c/b\u003e is similar to the capital if the number of roads connected to city \u003cb\u003eA\u003c/b\u003e is equal to the number of roads connected to the capital.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nOn each day during the vacation, the Chef wants to have a trip as follows. He chooses two cities \u003cb\u003eA\u003c/b\u003e and \u003cb\u003eB\u003c/b\u003e such that the Chef will visit city \u003cb\u003eB\u003c/b\u003e if he goes from \u003cb\u003eA\u003c/b\u003e to the capital using the shortest path. Then, the Chef will visit the cities on the shortest path from \u003cb\u003eA\u003c/b\u003e to \u003cb\u003eB\u003c/b\u003e through this path. Please note that \u003cb\u003eA\u003c/b\u003e may be equal to \u003cb\u003eB\u003c/b\u003e; that means the Chef will enjoy the day in a single city.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nThe Chef does not want to have \u003ci\u003esimilar\u003c/i\u003e trips. Two trips are considered \u003ci\u003esimilar\u003c/i\u003e if and only if\r\nthey both have the same number of visited cities and for each \u003cb\u003ei\u003c/b\u003e, the \u003cb\u003ei\u003c/b\u003e-th city visited in one trip is \u003ci\u003esimilar\u003c/i\u003e to the \u003cb\u003ei\u003c/b\u003e-th city visited in the other trip.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nThe Chef wants to have as many different, namely not \u003ci\u003esimilar\u003c/i\u003e, trips as possible. Help him count the maximum number of possible trips such that no two of them are similar.\r\n\u003cp\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\nThe first line of the input contains a single integer \u003cb\u003eN\u003c/b\u003e. The \u003cb\u003ei\u003c/b\u003e-th line of next \u003cb\u003eN\u003c/b\u003e-1 lines contains two space-separated integers \u003cb\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, denoting the \u003cb\u003ei\u003c/b\u003e-th road.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\nOutput a single line containing the maximum number of different trips.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\n1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 100000 (10\u003csup\u003e5\u003c/sup\u003e)\u003cbr\u003e\u003cb\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≠ \u003cb\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e\u003cbr\u003e\r\nEvery pair of different cities can be traveled by going through exactly one path of roads.\u003c/p\u003e\r\n\r\n\u003ch3\u003eSample\u003c/h3\u003e\r\n\u003cpre\u003e\r\n\u003cb\u003eInput\u003c/b\u003e:\r\n3\r\n2 1\r\n3 1\r\n\r\n\u003cb\u003eOutput\u003c/b\u003e:\r\n3\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\nIn the sample, the country consists of three cities.\r\nThere are two roads. The first road connects city 1 and city 2.\r\nThe second road connects city 1 and city 3.\r\nEach day, the Chef can choose the following possible trips:\r\n\u003c/p\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e\r\n\u003cb\u003eA\u003c/b\u003e \u003d 1, \u003cb\u003eB\u003c/b\u003e \u003d 1\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n\u003cb\u003eA\u003c/b\u003e \u003d 2, \u003cb\u003eB\u003c/b\u003e \u003d 2\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n\u003cb\u003eA\u003c/b\u003e \u003d 3, \u003cb\u003eB\u003c/b\u003e \u003d 3\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n\u003cb\u003eA\u003c/b\u003e \u003d 2, \u003cb\u003eB\u003c/b\u003e \u003d 1\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n\u003cb\u003eA\u003c/b\u003e \u003d 3, \u003cb\u003eB\u003c/b\u003e \u003d 1\r\n\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003cp\u003e\r\nHowever, since the trip (\u003cb\u003eA\u003c/b\u003e \u003d 2, \u003cb\u003eB\u003c/b\u003e \u003d 2) is similar to the trip (\u003cb\u003eA\u003c/b\u003e \u003d 3, \u003cb\u003eB\u003c/b\u003e \u003d 3),\r\nand the trip (\u003cb\u003eA\u003c/b\u003e \u003d 2, \u003cb\u003eB\u003c/b\u003e \u003d 1) is similar to the trip (\u003cb\u003eA\u003c/b\u003e \u003d 3, \u003cb\u003eB\u003c/b\u003e \u003d 1),\r\nthere are only three possible different trips for the Chef.\r\n\u003c/p\u003e\r\n"}}]}