Сity 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 的总和尽可能大。
输入
第一输入行包含整数 n (3 ≤ n ≤ 5000) — 城市中路口的数量。接下来的 n - 1 行列出所有道路,每行一条。每条道路都以一对整数 xi, yi (1 ≤ xi, yi ≤ n) 的形式给出——连接路口的索引。考虑索引从 1 到 n 的连接点。
保证给定的道路网络由具有 n 个顶点的无向树表示。
输出
在第一行打印整数 z — 查找对的数量。然后按照第一个分量 a 的递增顺序打印所有查找的对 (a, b)。
示例
输入 #1
5 1 2 2 3 3 4 4 5
输出 #1
3 1 3 2 2 3 1
输入 #2
10 1 2 2 3 3 4 5 6 6 7 7 4 8 9 9 10 10 4
输出 #2
6 1 8 2 7 3 6 6 3 7 2 8 1
注意
下图显示了第一个测试用例的答案。与“iMac D0naldz”餐厅的路口标记为红色,“Burger Bing”餐厅的路口标记为蓝色。