Новая социальная сеть (НСС) от 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\}$$$ — дерево. Вы должны найти максимальное паросочетание в этом двудольном графе.