В Берляндии наступила пора выборов. Фаворитами конечно являются партии зубликанцев и мумократов. Предвыборные кампании обеих партий включают в себя многочисленные митинги на n главных площадях столицы Берляндии. На каждой из n площадей конечно может митинговать только одна партия, иначе это может привести к беспорядкам. С другой стороны обе партии подали заявки на проведение огромного количества митингов так, что на всех площадях обязательно пройдут митинги. Теперь руководству столицы предстоит распределить площади между двумя партиями.

Некоторые пары площадей соединены (n - 1) двусторонними дорогами таким образом, что между любой парой площадей существует единственный способ попасть с одной площади на другую. Некоторые площади находятся на окраинах столицы, поэтому соединены дорогой лишь с одной другой площадью, такие площади называются тупиковыми.

Мэр столицы поручил распределить все площади между партиями таким образом, чтобы в тупиковых площадях было одинаковое количество митингов первой и второй партии. Гарантируется, что количество тупиковых площадей города чётно.

Для предотвращения возможных конфликтов между зубликанцами и мумократам было решено минимизировать количество дорог соединяющих площади с разными партиями. Вам как разработчику отдела распределения площадей предстоит определить это наименьшее количество.