Путешествие в Гексагонляндии

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

Гексагонляндия представляет собой бесконечное количество кварталов, каждый из которых является правильным шестиугольником. Кварталы расположены в виде регулярной сетки (см. рис. 1). Экскурсионные маршруты в Гексагонляндии проходят точно по линиям между кварталами и никогда не проходят через одну точку дважды. Все экскурсионные маршруты в Гексагонляндии замкнуты (заканчиваются в той точке, где они начинаются). Один из возможных экскурсионных маршрутов изображен на рисунке. Кружочком отмечено его начало. Заметим, что любой маршрут состоит из нескольких отрезков, каждый из которых равен стороне шестиугольника. Каждый маршрут можно задать, указав направление каждого отрезка. Всего существует 6 направлений: E - направление направо (на восток), W - направление налево (на запад), NE - вверх и вправо (северо-восток), NW - вверх и влево (северо-запад), SE - вниз и вправо (юго-восток), SW - вниз и влево (юго-запад). Например, маршрут на рисунке можно задать последовательностью направлений: "E NE E SE E SE E SE SW W SW W SW W NW W NW NE NW NE". Заметим, что пробелы можно опустить и записать: "ENEESEESEESESWWSWWSWWNWWNWNENWNE".

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

Входные данные

Во входном файле записана строка, описывающая маршрут. Длина строки не превосходит 30000 символов. Гарантируется, что входная строка корректно описывает некоторый экскурсионный маршрут.

Выходные данные

Во входной файл выведите два числа через пробел - количество кварталов, о которых рассказал экскурсовод, и количество кварталов, которые могли наблюдать экскурсанты.

Пример

Ввод

ENEESEESEESESWWSWWSWWNWWNWNENWNE

Вывод

8 7

Ремонт дорог

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

В королевстве имеется N городов. Некоторые из них соединены двусторонними дорогами. Дороги проложены таким образом, что из любого города можно добраться в любой другой, передвигаясь только по дорогам. Также верно, что не существует такого города, начав движение по дорогам из которого, можно вернуться назад в него же, не проходя ни по одной дороге дважды. Между каждой парой городов может быть не более одной дороги. Король решил провести ремонт всех дорог. Для этого он решил пригласить лучших иностранных специалистов. Иностранные специалисты работают бригадами.
В силу специфики национального менталитета каждая бригада починит все дороги на некотором пути от одного города до другого (каждая бригада чинит дороги лишь вдоль одного пути). С другой стороны, бригады не сильно ладят между собой, поэтому их пути (по которым они чинят дороги) не могут иметь общих дорог, но вполне могут иметь общие города. Королю известно, что плата за проделанную работу составит N*K+P, где N - количество городов в королевстве, K - количество приглашенных бригад, P - максимальная длина пути, вдоль которого осуществлялась починка дорог. В зависимости от того, сколько будет приглашено бригад, и как они распределят свою работу, плата за их работу будет различной. Разумеется, король хочет заплатить как можно меньше. Ваша задача указать ту минимальную сумму, за которую возможно починить все дороги в королевстве.

Входные данные

В первой строке входного файла содержится два натуральных числа N и M (2 <= N <= 10000; 1 <= M <= 9999), где N - количество городов в королевстве, а M - число дорог. Далее в M строках содержатся описания дорог. Каждое описание представляет собой пару чисел, обозначающих номера городов, которые соединяет дорога. Все числа в строках разделяются пробелами.

Выходные данные

В выходной файл выведите единственное число - минимальное количество денег, за которое король может починить все дороги в королевстве.

Пример

Ввод

6 5
1 6
6 3
6 2
2 4
5 2

Вывод

20