Phản xích

Cho một đồ thị có hướng không chu trình $G$ gồm $n$ đỉnh, đánh số từ $0$ đến $n-1$. Đồ thị có đúng $n$ cạnh, đánh số từ $0$ đến $n-1$. Cạnh số $i$ nối hai đỉnh $i$ và $(i+1)modn$, và có thể có hướng theo một trong hai chiều.

Chiều của các cạnh được cho bởi một xâu nhị phân $s_0{s}_1\dots s_{n-1}$:

• Nếu $s_i=0$ thì cạnh số $i$ hướng từ đỉnh $i$ đến đỉnh $(i+1)modn$.
• Nếu $s_i=1$ thì cạnh số $i$ hướng từ đỉnh $(i+1)modn$ đến đỉnh $i$.

Như vậy các đỉnh nằm trên một vòng tròn và mỗi cạnh nối hai đỉnh kề nhau trên vòng tròn đó.

Hai đỉnh $u$ và $v$ được gọi là so sánh được nếu trong đồ thị tồn tại một đường đi có hướng từ $u$ đến $v$ hoặc từ $v$ đến $u$. Một phản xích (antichain) là một tập các đỉnh mà bất kỳ hai đỉnh phân biệt nào trong tập đều không so sánh được với nhau. Kích thước của một phản xích là số đỉnh trong tập đó.

Hãy tìm kích thước của phản xích lớn nhất trong đồ thị $G$.

Dữ liệu đảm bảo đồ thị đã cho là không có chu trình.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s_0{s}_1\dots s_{n-1}$ gồm các ký tự '0' và '1'. Độ dài của xâu chính là số đỉnh (và số cạnh) $n$ của đồ thị.

Dữ liệu ra

In ra một số nguyên duy nhất, là kích thước của phản xích lớn nhất trong đồ thị $G$.

Ràng buộc

• $2\le n\le {10}^6$.
• Đồ thị được đảm bảo không có chu trình.

Ví dụ