← 返回题目列表

Codeforces · 212/E

E. IT 餐厅

中文机器翻译题面 查看原题

С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”餐厅的路口标记为蓝色。