Palindromic Partitions

Given a string (s) consisting only of lowercase letters, your task is to partition the string into substrings such that every substring is a palindrome. A string is a palindrome if it reads the same forwards and backwards. Use a backtracking approach to generate all possible palindromic partitions.

For example, if (s = "aba"), the valid partitions are:

• \(\{a, b, a\}\)
• \(\{aba\}\)

You need to read the input from standard input (stdin) and output the result to standard output (stdout) as described below.

inputFormat

The input consists of a single line containing the string (s). The string contains only lowercase letters. ((0 \leq |s| \leq 100))

outputFormat

The first line of the output should contain a single integer representing the total number of palindromic partitions. Each of the following lines should output one partition, where the palindromic substrings are separated by a single space. The order of the partitions should follow the order in which they are generated by the backtracking algorithm.## sample

aba

2
a b a
aba