Вам задан ориентированный ациклический граф 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.
Выходные данные
Выведите единственное целое число — размер максимальной антицепи графа G.
Примечание
Рассмотрим первый тестовый пример. Ребра графа G: 0 → 1, 1 → 2, 0 → 2. В качестве максимальной антицепи можно выбрать множество вершин [0]. Большую по размеру антицепь выбрать не получится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
001
|
1
|
|
2
|
110010
|
3
|