贝尔兰政府决定改善与邻国的关系。首先,决定修建新的道路,以便从贝尔兰的每个城市和邻国都可以到达其他所有城市。贝尔兰及其邻国共有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