CF212E IT Restaurants

N 市在道路、食品和 IT 基础设施方面存在巨大问题。该市共有 $n$ 个路口，路口间由双向道路连接。$n - 1$ 条道路组成了 N 市的道路网，您可以通过这些道路从一个路口到达另一个路口。道路网构成了一棵无向树。 最近，市长想出了一个既能解决食品问题，又能解决 IT 基础设施问题的办法！他决定在城市路口为 IT 专业人员开设两家著名咖啡馆品牌的餐厅：iMac D0naldz 和 Burger Bing。由于两个品牌的老板关系不佳，因此不能在相邻路口开设不同品牌的餐厅。具体要求如下： - 每个路口最多开设一家餐厅； - 一家餐厅要么属于 iMac D0naldz，要么属于 Burger Bing； - 两个品牌各拥有至少一家餐厅； - 任何相邻的路口不能开设不同品牌的餐厅。 市长将从每家餐厅收取一大笔税金，因此他希望餐厅的总数越多越好。 请帮助市长找出所有的 $(a,b)$ 对，即 $a$ 家餐厅属于 "iMac D0naldz"，$b$ 家餐厅属于 "Burger Bing"，并且使 $a+b$ 尽可能大。

第一行输入一个整数 $n$ $(3\le n\le5000)$，表示城市中路口的数量。接下来的 $n - 1$ 行列出了所有道路。每条道路都由一对整数 $x_i, y_i$ $(1\le x_i, y_i\le n)$ 表示。$x_i,y_i$ 为路口的编号。路口编号从 $1$ 到 $n$。 题目保证，给定的道路网是一棵无向树，共有 $n$ 个顶点。

第一行输出一个整数 $z$ 表示找到的配对数。然后按照 $a$ 的递增顺序输出所有满足条件的 $(a,b)$ 对。

下图展示了第一个测试样例的答案。标红的路口表示 iMac D0naldz 品牌的餐厅，标蓝的路口表示 Burger Bing 品牌的餐厅。 :::align{center}  :::