Problem description


Długość LCS z literką 'a'
(lcs-with-a)
Memory limit: 256 MB
Time limit: 2.00 s

Zadanie jest tak hardcorowe, że nie ma co owijać w bawełnę i silić się na historyjkę. Masz dane dwa ciągi liter, a Twoim zadaniem jest znaleźć długość ich najdłuższego wspólnego podciągu, który zawiera w sobie chociaż jedno wystąpienie litery a.

Wejście

W dwóch wierszach standardowego wejścia znajdują się dwa ciągi małych liter alfabetu angielskiego.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba naturalna, oznaczająca długość najdłuższego wspólnego podciągu słów podanych na wejściu, który zawiera literę a, lub słowo NIE, jeśli taki podciąg nie istnieje.

Ograniczenia

Oba słowa są niepuste oraz niedłuższe niż 5000 znaków.

Przykład

Input Output
bbab
aba
2