← 返回题目列表

Codeforces · 25/D

D. 道路不仅在贝尔兰

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

贝尔兰政府决定改善与邻国的关系。首先,决定修建新的道路,以便从贝尔兰的每个城市和邻国都可以到达其他所有城市。贝尔兰及其邻国共有n个城市,正好有n-1条双向道路。由于最近的金融危机,柏林政府资金紧张,为了修建新公路,不得不关闭部分现有公路。每天都有可能关闭一条现有道路并立即修建一条新道路。你的任务是确定重建道路需要多少天,以便从每个城市可以到达所有其他城市,并制定关闭旧道路和修建新道路的计划。

输入

第一行包含整数 n (2 ≤ n ≤ 1000) — Berland 及其邻国的城市数量。接下来的 n - 1 行包含道路的描述。每条道路由两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) 描述 - 道路连接的一对城市。两个城市之间不能有多于一条道路。没有道路将城市与其本身连接起来。

输出

输出答案,数字 t — 重建道路以便从每个城市到达所有其他城市所需的最少天数。然后输出t行——关闭旧路和修建新路的计划。每行应该以 i j u v 的格式描述一天——这意味着城市 i 和 j 之间的道路被封闭,而城市 u 和 v 之间的一条新道路被修建。城市从1开始编号。如果答案不唯一,则输出任意。

示例

输入 #1

2
1 2

输出 #1

0

输入 #2

7
1 2
2 3
3 1
4 5
5 6
6 7

输出 #2

1
3 1 3 7