拜特朗政府已经决定，现在是时候将他们的小国家与互联网连接起来，以便所有公民都能参加节目比赛，观看可爱猫的视频。当是时候建设这个国家的网络骨干时，他们给互联网乐观主义者公司分配了连接所有 N 个拜特兰德的电脑。这些连接是作为计算机对之间的直接连接，使任何一对计算机都通过一系列的链接连接起来。

拜特朗是一个发展中国家，因此，为了将成本降到最低，网络拓扑是以树的形式构建的(即有 N-1 个计算机之间的直接连接)。为时已晚，人们意识到这一解决方案存在严重缺陷。如果只有一个链接断了，那么拜特兰德的计算机就会被分割，这样一些计算机就不能互相通信了！为了提高拜特朗网络的可靠性，人们决定至少要容忍单个链路中断。你的任务是帮助互联网乐观主义者公司以最便宜的方式改进网络。给出了拜特朗的网络拓扑(即 N-1 个计算机对是通过直接链接连接的)，找到需要添加的最少数量的链接，以便如果任何单个链接中断，网络仍将被连接。

输入的第一行包含一个正整数 N(N\geq 3)，表示拜特兰德的计算机数量。为了简单起见，所有的计算机都是从 1 到 N。以下 N-1 行包含一对整数。a 和 b(1≤a, b≤n, a\neq b)，它描述计算机之间的直接链接 a 和 b。

在输出的第一行只有一个整数k，表示应该添加到网络中的最少链接数量。在下列每一项中都有对整数 a 和 b(1\leq a ,b\leq n,a\neq b) 表示应该通过链接连接的计算机数量。链接可以按任何顺序写入。如果有一个以上的解决方案，您的程序应该输出其中的任何一个。

3 \le N \le 500000。

BalticOI