
"""simple docstring"""


from __future__ import annotations






def      lowerCAmelCase_     (	snake_case_	:    Any    )     ->str:
			global graph, reversed_graph, scc, component, visit, stack
			if visit[u]:
						return
			lowerCamelCase__			:  str  =True
			for v in graph[u]:
						dfs(snake_case_    )
			stack.append(snake_case_    )






def      lowerCAmelCase_     (	snake_case_	:    Any    )     ->List[str]:
			global graph, reversed_graph, scc, component, visit, stack
			if visit[u]:
						return
			lowerCamelCase__			:  Tuple  =True
			component.append(snake_case_    )
			for v in reversed_graph[u]:
						dfsa(snake_case_    )






def      lowerCAmelCase_     (	)     ->List[Any]:
			global graph, reversed_graph, scc, component, visit, stack
			for i in range(snake_case_    ):
						dfs(snake_case_    )
			lowerCamelCase__			:  List[Any]  =[False] * n
			for i in stack[::-1]:
						if visit[i]:
									continue
						lowerCamelCase__			:  List[Any]  =[]
						dfsa(snake_case_    )
						scc.append(snake_case_    )
			return scc


if __name__ == "__main__":
							# n - no of nodes, m - no of edges
							lowerCAmelCase	,  lowerCAmelCase			=		list(map(int, input().strip().split()))

							lowerCAmelCase			=		[[] for _ in range(n)]  # graph
							lowerCAmelCase			=		[[] for i in range(n)]  # reversed graph
							# input graph data (edges)
							for _ in range(m):
														lowerCAmelCase	,  lowerCAmelCase			=		list(map(int, input().strip().split()))
														graph[u].append(v)
														reversed_graph[v].append(u)

							lowerCAmelCase			=		[]
							lowerCAmelCase			=		[False] * n
							lowerCAmelCase			=		[]
							lowerCAmelCase			=		[]
							print(kosaraju())

"""simple docstring"""


def      lowerCAmelCase_     (	snake_case_	:    str    )     ->int:
			lowerCamelCase__			:  Optional[Any]  =len(snake_case_    )
			lowerCamelCase__			:  Any  =[0] * length
			lowerCamelCase__			:  str  =[[False for i in range(snake_case_    )] for j in range(snake_case_    )]
			for i, c in enumerate(snake_case_    ):
						lowerCamelCase__			:  Optional[Any]  =i
						for j in range(i + 1    ):
									if c == string[j] and (i - j < 2 or is_palindromic[j + 1][i - 1]):
												lowerCamelCase__			:  int  =True
												lowerCamelCase__			:  Tuple  =min(snake_case_							,					0 if j == 0 else (cut[j - 1] + 1)    )
						lowerCamelCase__			:  Any  =mincut
			return cut[length - 1]


if __name__ == "__main__":
							lowerCAmelCase			=		input("""Enter the string: """).strip()
							lowerCAmelCase			=		find_minimum_partitions(s)
							print(f"""Minimum number of partitions required for the '{s}' is {ans}""")