F. Новый год и социальная сеть
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Новая социальная сеть (НСС) от Donghyun содержит $$$n$$$ пользователей с номерами $$$1, 2, \ldots, n$$$. Их сеть представляет собой дерево, поэтому между пользователем существует $$$n-1$$$ прямых соединений. Каждый пользователь может связаться с другим пользователем, используя некоторую последовательность прямых соединений. Мы будем обозначать эту первичную сеть как $$$T_1$$$.

Чтобы предотвратить возможную поломку сервера, Donghyun создал резервную сеть $$$T_2$$$, которая соединяет тех же $$$n$$$ пользователей как дерево. Если система выходит из строя, ровно одно ребро $$$e \in T_1$$$ становится непригодным для использования. В этом случае Donghyun защитит ребро $$$e$$$, выбрав другое ребро $$$f \in T_2$$$, и добавит его в существующую сеть. Это новое ребро должно сделать сеть опять связной.

Donghyun хочет выбрать заменяющее ребро $$$f \in T_2$$$ для максимально возможного количества ребер $$$e \in T_1$$$. Однако, поскольку резервная сеть $$$T_2$$$ является хрупкой, $$$f \in T_2$$$ может быть выбрано в качестве замещающего ребра для не более одного ребра в $$$T_1$$$. С этим ограничением Donghyun хочет защитить как можно больше ребер в $$$T_1$$$.

Формально, пусть $$$E(T)$$$ — множество ребер дерева $$$T$$$. Рассмотрим двудольный граф с двумя долями $$$E(T_1)$$$ и $$$E(T_2)$$$. Для $$$e \in E(T_1), f \in E(T_2)$$$, существует ребро, соединяющее $$$\{e, f\}$$$ тогда и только тогда, когда граф $$$T_1 - \{e\} + \{f\}$$$ — дерево. Вы должны найти максимальное паросочетание в этом двудольном графе.

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

В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 250\,000$$$) — размер обоих деревьев.

В следующих $$$n-1$$$ строках записано по два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$). Эти два числа обозначают ребро из $$$T_1$$$.

В следующих $$$n-1$$$ строках записано по два целых числа $$$c_i$$$ и $$$d_i$$$ ($$$1 \le c_i, d_i \le n$$$). Эти два числа обозначают ребро из $$$T_2$$$.

Гарантируется, что оба этих множества ребер — это деревья на $$$n$$$ вершинах.

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

В первой строке выведите целое число $$$m$$$ ($$$0 \leq m < n$$$), размер максимального по размеру паросочетания.

В следующих $$$m$$$ строках выведите по четыре целых числа $$$a_i, b_i, c_i, d_i$$$. Эти четыре целых числа описывают, что ребро $$$(a_i, b_i)$$$ из $$$T_1$$$ объединено в пару с ребром $$$(c_i, d_i)$$$ из $$$T_2$$$.

Все выведенные ребра должны принадлежать соответствующим деревьям, и все выведенные ребра одного дерева должны быть различными. Если убирают ребро $$$(a_i, b_i)$$$ из $$$T_1$$$ и добавляют ребро $$$(c_i, d_i)$$$ из $$$T_2$$$, то сеть должна оставаться связной. Порядок выведенных пар и порядок вершин внутри ребер не имеет значения.

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

Примеры
Входные данные
4
1 2
2 3
4 3
1 3
2 4
1 4
Выходные данные
3
3 2 4 2
2 1 1 3
4 3 1 4
Входные данные
5
1 2
2 4
3 4
4 5
1 2
1 3
1 4
1 5
Выходные данные
4
2 1 1 2
3 4 1 3
4 2 1 4
5 4 1 5
Входные данные
9
7 9
2 8
2 1
7 5
4 7
2 4
9 6
3 9
1 8
4 8
2 9
9 5
7 6
1 3
4 6
5 3
Выходные данные
8
4 2 9 2
9 7 6 7
5 7 5 9
6 9 4 6
8 2 8 4
3 9 3 5
2 1 1 8
7 4 1 3