Шахова дошка
Обмеження: 2 сек., 256 МіБ
Зеник і Марічка хильнули трохи соку і вирішили, що хочуть навчитись добре грати шахи.
Для цього їм спочатку потрібно мати шахову дошку — дошку із 8-ми рядків та 8-ми стовпців, яка складається із чорних та білих клітинок. Клітинка у першому рядку першого стовпця має бути білою, і будь-які дві сусідні по стороні клітинки мають мати різний колір.
Зеник знайшов у підвалі якусь дошку, яка виявилась правильних розмірів, проте у ній клітинка на перетині i-го рядка та j-го стовпця розфарбована у колір aij. Він вирішив перетворити цю дошку у правильну використовуючи послідовність дій. Кожна дія може бути одного із двох типів:
Зеник міняє місцями кольори двох сусідніх по стороні клітинок дошки. На це він витрачає рівно 1 хвилину.
Зеник просить Марічку поміняти місцями кольори двох сусідніх по діагоналі клітинок дошки. Оскільки Марічка добре організована, вона робить це миттєво, тобто витрачає 0 хвилин.
Зенику цікаво, чи зможе він утворити правильну шахову дошку, і якщо так, то за яку мінімальну кількість хвилин?
Вхідні дані
У 8 рядках задано по 8 символів у кожному, які позначають колір aij клітинки на перетині i-го рядка та j-го стовпця початкової дошки. Символ
W
позначає білу клітинку, а символ B
—
чорну.
Вихідні дані
У першому рядку виведіть TAK
, якщо Зеник та Марічка
можуть отримати правильну шахову дошку діями, описаними в умові. У
протилежному випадку виведіть NI
.
У разі позитивної відповіді у другому рядку виведіть мінімальну кількість хвилин, за яку вони можуть виконати свою ціль.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
WWWWWWWW BBBBBBBB WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBB WBWBWBWB BWBWBWWW | TAK 5 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
WWWWWWWW WWWWWWWW WWWWWWWW WWWWWWWW WWWWWWWW WWWWWWWW WWWWWWWW WWWWWWWW | NI |