Все жители Берляндии ждут беспрецедентного турне волшебника в голубом вертолете по городам Берляндии!

Известно, что в Берляндии n городов, некоторые пары которых соединены двусторонними дорогами. Каждая пара городов соединена не более чем одной дорогой. Не гарантируется, что дорожная сеть связна, то есть возможно, что из какого-то города невозможно добраться до других, двигаясь по дорогам.

Турне волшебника будет состоять из туров. Во время каждого тура:

• волшебник высадится в некотором городе x с вертолета;
• даст представление и бесплатно покажет кино в городе x;
• проедет по дороге в соседний город y;
• даст представление и бесплатно покажет кино в городе y;
• проедет по дороге в соседний с y город z;
• даст представление и бесплатно покажет кино в городе z;
• улетит на вертолете из города z.

Известно, что волшебник не любит путешествовать по дорогам: по каждой дороге он может проехать лишь единожды (независимо от направления). Иными словами для дороги между a и b он может либо проехать один раз из a в b, либо проехать один раз из b в a, либо вообще не проезжать по этой дороге.

Волшебник хочет организовать максимальное количество туров, не нарушив правила изложенные выше. Помогите волшебнику!

Обратите внимание, что волшебник может посещать один город многократно, ограничение на посещения касается исключительно дорог.