Với một cây có gốc $A$ và một số nguyên $B \ge 2$, ta định nghĩa cây không gốc $A * B$ như sau:

• Sao chép cây $A$ thành $B$ bản sao $A_1, A_2, \ldots, A_B$, sau đó với mọi $i$ ($1 \le i < B$), nối gốc của $A_i$ với gốc của $A_{i+1}$ bằng một cạnh.

Cho trước một cây không gốc $C$, hãy tìm một cây có gốc $A$ và một số nguyên $B \ge 2$ sao cho $C = A * B$.

Dữ liệu đảm bảo rằng luôn tồn tại cây có gốc $A$ và số nguyên $B \ge 2$ thỏa mãn $C = A * B$.

Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào.

Đối với hai cây không gốc $T_1$ và $T_2$, ta coi $T_1 = T_2$ nếu chúng có cùng cấu trúc (bỏ qua nhãn của các đỉnh).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ là số đỉnh của cây $C$. $(2 \le N \le 100\,000)$

$N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ là hai đầu mút của một cạnh trong cây $C$. $(1 \le u, v \le N)$

Dữ liệu ra

Dòng đầu tiên in ra số nguyên $B$.

Dòng thứ hai in ra số nguyên $M$ là số đỉnh của cây $A$.

$M-1$ dòng tiếp theo, mỗi dòng in ra hai số nguyên $u, v$ là hai đầu mút của một cạnh trong cây $A$. $(1 \le u, v \le M)$

Gốc của cây $A$ là đỉnh $1$.

Ví dụ

Dữ liệu vào 1

4
1 2
2 3
3 4

Dữ liệu ra 1

4
1

Dữ liệu vào 2

6
1 2
1 3
1 4
4 5
4 6

Dữ liệu ra 2

2
3
1 2
1 3