Однажды мама попросила Петю разобрать игрушки и избавиться от части из них. Петя нашел целую коробку игрушечных пауков. Они очень ему дороги, и мальчик не хочет их выкидывать. Петя придумал хитрый план: он склеит всех паучков и подвесит к потолку. Также он знает, что чем ниже будет свисать эта конструкция, тем больше понравится маме, и она не станет выкидывать его самые любимые игрушки. Помогите Пете осуществить его план.

Паук состоит из k бусинок, связанных k - 1 ниточкой. Каждая ниточка соединяет две различные бусинки, при этом любая пара бусинок, составляющих паука, либо непосредственно связана ниточкой, либо связана некоторой цепочкой из ниточек и бусинок.

Склеивать пауков Петя может непосредственно за бусинки. Длина каждой нитки равна 1. Размерами бусинок можно пренебречь. Поэтому можно считать, что склеивание пауков происходит путем отождествления некоторых бусинок (см. рисунок). При этом конструкция, получаемая при склеивании, также должна представлять собой паука, т.е. для нее должны выполняться указанные свойства.

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

На рисунке изображено 2 паучка из второго примера. К бусинке номер 2 первого паучка мы приклеим второго паучка за бусинку с номером 1. На рисунке выделены ниточки в паучках, которые образуют последовательность ниточек максимальной длины.