После просмотра нового сериала «Игра в кальмара» Маштали и Соруш решили провести свою собственную «Игру в кальмара»! Соруш согласился быть ведущим и предоставить деньги для приза победителю, а Маштали стал фронтменом!
\(m\) игроков зарегистрировались для участия в играх, чтобы выиграть большой приз, но когда Маштали узнал, каким огромным будет приз победителя, он решил убить устранить всех игроков, чтобы забрать деньги себе!
Вот как злой Маштали собирается уничтожить игроков:
Дано некорневое дерево с \(n\) вершинами. У каждого игрока есть \(2\) специальные вершины \(x_i\) и \(y_i\).
За одну операцию Маштали может выбрать любую вершину \(v\) дерева. Затем для каждого оставшегося игрока \(i\) он находит вершину \(w\) на простом пути из \(x_i\) в \(y_i\), которая ближе всего к \(v\). Если \(w\ne x_i\) и \(w\ne y_i\), игрок \(i\) будет устранен.
Теперь Маштали задался вопросом: «Какое минимальное количество операций я должен выполнить, чтобы устранить всех игроков и забрать деньги себе?».
Поскольку он думал только о деньгах, он не смог решить задачу самостоятельно и обратился к вам за помощью!
Выходные данные
Выведите минимальное количество операций, которые Маштали должен выполнить.
Если Маштали никак не может устранить всех игроков, выведите \(-1\).