Для корневого дерева $A$ и целого числа $B \ge 2$ определим дерево без корня $A * B$ следующим образом:

• Создадим $B$ копий дерева $A$: $A_1, A_2, \ldots, A_B$. Для каждого $i$ от $1$ до $B-1$ соединим корень дерева $A_i$ с корнем дерева $A_{i+1}$ ребром.

Дано дерево без корня $C$. Найдите корневое дерево $A$ и целое число $B \ge 2$ такие, что $C = A * B$.

Гарантируется, что входные данные всегда допускают существование таких $A$ и $B$.

Если существует несколько возможных ответов, выведите любой из них.

Два дерева без корня $T_1$ и $T_2$ считаются равными ($T_1 = T_2$), если они изоморфны (то есть их структура совпадает, если не учитывать номера вершин).

Входные данные

В первой строке задано количество вершин $N$ в дереве $C$. $(2 \le N \le 100\,000)$

В следующих $N-1$ строках заданы ребра дерева $C$, каждое из которых описывается двумя целыми числами $u$ и $v$, разделенными пробелом. $(1 \le u, v \le N)$

Выходные данные

В первой строке выведите целое число $B$.

Во второй строке выведите количество вершин $M$ в дереве $A$.

В следующих $M-1$ строках выведите ребра дерева $A$, каждое из которых описывается двумя целыми числами $u$ и $v$, разделенными пробелом. $(1 \le u, v \le M)$

Корнем дерева $A$ является вершина $1$.

Примеры

Input 1

4
1 2
2 3
3 4

Output 1

4
1

Input 2

6
1 2
1 3
1 4
4 5
4 6

Output 2

2
3
1 2
1 3