짝수 회문 분할

어떤 단어를 거꾸로 읽어도 원래와 같으면 그 단어를 회문이라고 한다. 회문의 글자 수가 양의 짝수이면 그 회문을 짝수 회문이라고 한다.

예를 들어 abaaba는 짝수 회문이다.

단어의 짝수 회문 분할이란, 그 단어를 앞에서부터 연속된 여러 조각으로 나누되 각 조각이 모두 짝수 회문이 되도록 하는 분할을 말한다.

예를 들어 단어 bbaabbaabbbaaaaaaaaaaaabbbaa는 bbaabb + aabbbaaaaaaaaaaaabbbaa처럼 2개의 조각으로 나눌 수 있고, bb + aa + bb + aa + bb + baaaaaaaaaaaab + bb + aa처럼 8개의 조각으로도 나눌 수 있다. 첫 번째 분할은 짝수 회문의 개수가 가능한 한 가장 적고, 두 번째 분할은 가장 많다. 따라서 이 단어의 최소 분할 개수는 2, 최대 분할 개수는 8이다.

한 단어는 서로 다른 짝수 회문 분할을 여러 개 가질 수도 있고, 하나도 가지지 못할 수도 있다.

단어가 주어졌을 때, 그 단어를 짝수 회문들로 분할할 수 있는지 판정하여라. 분할할 수 없으면 불가능함을 알리고, 분할할 수 있으면 모든 분할 방법 중 짝수 회문 개수의 최솟값과 최댓값을 구하여라.

입력은 1글자 이상 200글자 이하의 영어 소문자로만 이루어진 단어 하나로 주어진다. 단어는 글자 사이에 공백 없이 한 줄에 쓰여 있다.

단어를 짝수 회문들로 분할할 수 없으면 NIE("아니오"라는 뜻) 한 단어만 출력한다.

분할할 수 있으면 두 줄을 출력한다.

• 첫째 줄에는 그 단어를 짝수 회문으로 분할했을 때 짝수 회문 개수의 최솟값을 출력한다.
• 둘째 줄에는 짝수 회문 개수의 최댓값을 출력한다.