You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

每个星球上都有自己的夜之国，为了方便出行，kuro希望修建一些铁路联通不同星球上的夜之国。

kuro选定$n$个星球和$n$条铁路，如果将每个星球看成一个点，那么铁路可以看成连接两个星球的边，这些点和边构成一张简单连通无向图（无自环、无重边、图是连通的）。

然而kuro发现，自己剩下的钱不够把所有的铁路的两个方向开通，只能把每条铁路的某一个方向开通，也就是把这张无向图变成有向图。

特别的，kuro希望所有星球的的入度的方差和最小，你需要给出一个每一条铁路开通方向的具体方案，满足kuro的想法

入度指在一张有向图中，指向该点的边的条数

在本题中，我们的方差和取以下定义：设顶点 i 的入度为 $\text{in}_i$，

$\sum_{i=1}^{n} (\text{in}_i - \frac{(\Sigma \text{in})}{n})^2$

Input Format

第一行输入一个整数 $n \,(3 \leq n \leq 10^5)$，表示图中顶点数（顶点从 1 到 $n$ 编号）。

接下来 $n$ 行，每行包含两个整数 $u, v \,(1 \le u, v \le n,\; u \neq v)$，表示在顶点 $u$ 和顶点 $v$ 之间存在一条无向边。

题目保证给定的图是简单连通的（无自环、无重边、整图连通）

Output Format

第一行输出一个整数，表示最小的方差和的值。

接下来 $n$ 行，每行包含两个整数 $x, y$，表示将原图中的某条无向边定向为 $x \to y$。

你可以以任何顺序输出这些边，如果有多种方案使得方差和最小，你可以输出任意一种。

Sample

输入 #1

3 
1 2
2 3 
3 1

输出 #1

0 
1 2
2 3 
3 1

样例说明

这三条边构成一个三角形，显然可以以顺时针或逆时针标边使得其入度都为1，方差和为0