E. Антицепь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Операция x mod y обозначает взятие остатка от деления числа x на число y.

Назовем две вершины u и v в графе G сравнимыми, если существует путь в графе из u в v, либо из v в u. Назовем антицепью множество вершин графа G, в котором любые две различные вершины не являются сравнимыми. Размером антицепи назовем количество вершин в соответствующем множестве. Назовем антицепь максимальной, если в графе нет антицепей с большим размером.

Вам требуется найти размер максимальной антицепи в графе G.

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

В первой строке записана последовательность символов s0s1... sn - 1 (2 ≤ n ≤ 106), состоящая из нулей и единиц. Длина строки (число n) соответствует количеству вершин и ребер в графе G. Если символ si (i ≥ 0) равен 0, то ребро между вершинами i и (i + 1) mod n ориентировано в направлении от i-ой вершины к вершине (i + 1) mod n, иначе — в противоположную сторону.

Гарантируется, что заданный граф ациклический.

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

Выведите единственное целое число — размер максимальной антицепи графа G.

Примеры
Входные данные
001
Выходные данные
1
Входные данные
110010
Выходные данные
3
Примечание

Рассмотрим первый тестовый пример. Ребра графа G: 0 → 1, 1 → 2, 0 → 2. В качестве максимальной антицепи можно выбрать множество вершин [0]. Большую по размеру антицепь выбрать не получится.