Antichain

题意翻译

有一个$n$个点（$n<=10^6$）的$0…n-1$标号的$DAG$，有$n$条端点为$i$和$(i+1)\%n$的有向边（方向是给定的，保证一定会构成一个$DAG$），求最长反链。 一个“反链”定义为一个点的集合，使得这个集合内任意两个点不会互相到达。 输入格式 一行一个长为$n$的01串，若第$i$位（$i\in[0,n-1]$）是0则表示$i$到$(i+1)\%n$有连边，否则$(i+1)\%n$到$i$有连边。 输出格式 一行一个整数，图的最长反链。

题目描述

You have a directed acyclic graph $ G $ , consisting of $ n $ vertexes, numbered from $ 0 $ to $ n-1 $ . The graph contains $ n $ edges numbered from $ 0 $ to $ n-1 $ . An edge with number $ i $ connects vertexes $ i $ and $ (i+1) mod n $ , and it can be directed in either direction (from $ i $ to $ (i+1) mod n $ , or vise versa). Operation $ x mod y $ means taking the remainder after dividing number $ x $ by number $ y $ . Let's call two vertexes $ u $ and $ v $ in graph $ G $ comparable if the graph contains a path either from $ u $ to $ v $ or from $ v $ to $ u $ . We'll assume that an antichain is a set of vertexes of graph $ G $ , where any two distinct vertexes are not comparable. The size of an antichain is the number of vertexes in the corresponding set. An antichain is maximum if the graph doesn't have antichains of a larger size. Your task is to find the size of the maximum antichain in graph $ G $ .

输入输出格式

输入格式

The first line contains the sequence of characters $ s_{0}s_{1}...\ s_{n-1} $ $ (2<=n<=10^{6}) $ , consisting of numbers zero and one. The length of the line (number $ n $ ) corresponds to the number of vertexes and edges in graph $ G $ . If character $ s_{i} $ $ (i>=0) $ equals $ 0 $ , then the edge between vertexes $ i $ and $ (i+1) mod n $ is directed from the $ i $ -th vertex to the $ (i+1) mod n $ -th one, otherwise — to the opposite point. It is guaranteed that the given graph is acyclic.

输出格式

Print a single integer — the size of the maximum antichain of graph $ G $ .

输入输出样例

输入样例 #1

001

输出样例 #1

1

输入样例 #2

110010

输出样例 #2

3

说明

Consider the first test sample. The graph's $ G $ edges are: $ 0→1 $ , $ 1→2 $ , $ 0→2 $ . We can choose the set of vertexes $ [0] $ as the maximum antichain. We cannot choose an antichain of larger size.