Новая социальная сеть (НСС) от 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\}\) — дерево. Вы должны найти максимальное паросочетание в этом двудольном графе.
Выходные данные
В первой строке выведите целое число \(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\), то сеть должна оставаться связной. Порядок выведенных пар и порядок вершин внутри ребер не имеет значения.
Если есть несколько возможных решений, вы можете вывести любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|
|
3
|
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
|