CF212E.IT Restaurants

Сity N. has a huge problem with roads, food and IT-infrastructure. In total the city has n junctions, some pairs of them are connected by bidirectional roads. The road network consists of n - 1 roads, you can get from any junction to any other one by these roads. Yes, you're right — the road network forms an undirected tree.

Recently, the Mayor came up with a way that eliminates the problems with the food and the IT-infrastructure at the same time! He decided to put at the city junctions restaurants of two well-known cafe networks for IT professionals: "iMac D0naldz" and "Burger Bing". Since the network owners are not friends, it is strictly prohibited to place two restaurants of different networks on neighboring junctions. There are other requirements. Here's the full list:

• each junction must have at most one restaurant;
• each restaurant belongs either to "iMac D0naldz", or to "Burger Bing";
• each network should build at least one restaurant;
• there is no pair of junctions that are connected by a road and contains restaurants of different networks.

The Mayor is going to take a large tax from each restaurant, so he is interested in making the total number of the restaurants as large as possible.

Help the Mayor to analyze the situation. Find all such pairs of (a, b) that a restaurants can belong to "iMac D0naldz", b restaurants can belong to "Burger Bing", and the sum of a + b is as large as possible.

城市 N 在道路、食品和 IT 基础设施方面存在严重问题。该城市共有 $ n $ 个路口，其中某些路口对之间由双向道路连接。整个路网包含 $ n-1 $ 条道路，且任意两个路口之间均可通过这些道路相互到达。没错——该路网构成一棵无向树。

最近，市长想出了一个能同时解决食品与 IT 基础设施问题的方案！他决定在城市的各个路口处开设两家知名面向 IT 从业者的连锁餐饮品牌餐厅：“iMac D0naldz” 和 “Burger Bing”。由于两家品牌所有者关系不睦，严格禁止在相邻（即由一条道路直接相连）的两个路口上分别开设不同品牌的餐厅。此外，还有其他若干要求。全部要求如下：

• 每个路口最多只能开设一家餐厅；
• 每家餐厅必须属于“iMac D0naldz”或“Burger Bing”其中之一；
• 两个品牌都至少需开设一家餐厅；
• 不存在一对由道路直接相连的路口，其上分别开设了不同品牌的餐厅。

市长将向每家餐厅征收高额税款，因此他希望使餐厅总数尽可能多。

请协助市长分析这一情况：找出所有满足条件的数对 $ (a,,b) $，使得其中 $ a $ 家餐厅属于“iMac D0naldz”，$ b $ 家餐厅属于“Burger Bing”，且总和 $ a + b $ 达到最大可能值。

The first input line contains integer n (3 ≤ n ≤ 5000) — the number of junctions in the city. Next n - 1 lines list all roads one per line. Each road is given as a pair of integers x__i, y__i (1 ≤ x__i, y__i ≤ n) — the indexes of connected junctions. Consider the junctions indexed from 1 to n.

It is guaranteed that the given road network is represented by an undirected tree with n vertexes.

第一行输入包含一个整数 $n$（$3 \leq n \leq 5000$）—— 表示城市中路口的数量。接下来的 $n-1$ 行每行描述一条道路。每条道路由一对整数 $x_i,\,y_i$（$1 \leq x_i,\,y_i \leq n$）给出，表示相连的两个路口的编号。路口编号从 $1$ 到 $n$。

保证所给的道路网络构成一棵含 $n$ 个顶点的无向树。

Print on the first line integer z — the number of sought pairs. Then print all sought pairs (a, b) in the order of increasing of the first component a.

第一行输出整数 $z$ —— 所求的数对个数。然后按第一个分量 $a$ 的升序依次输出所有所求的数对 $(a,\,b)$。

The figure below shows the answers to the first test case. The junctions with "iMac D0naldz" restaurants are marked red and "Burger Bing" restaurants are marked blue.

下图展示了第一个测试用例的答案。标有 “iMac D0naldz” 餐厅的路口用红色标记，标有 “Burger Bing” 餐厅的路口用蓝色标记。