Задачи
Химия!!!
Химия!!!
Вася и Серёжа играют в следующую игру. В некоторых клетках клетчатого листка Серёжа рисует один из символов "\textbf{H}", "\textbf{O}", "\textbf{N}" или "\textbf{C}", после чего Вася должен провести между некоторыми находящимися в соседних клетках символами линии так, чтобы получилось корректное изображение химической молекулы. К сожалению, Серёжа любит рисовать много символов, и Вася не может сразу определить, возможно ли вообще нарисовать линии нужным способом. Помогите ему написать программу, которая даст ответ на этот вопрос.
В этой задаче проведенные между символами химических элементов линии будем считать корректным изображением молекулы, если они удовлетворяют следующим условиям:
\begin{itemize}
\item каждая линия соединяет символы, нарисованные в соседних (по стороне) клетках,
\item между каждой парой символов проведено не более одной линии,
\item от каждого элемента отходит ровно столько линий, какова валентность этого элемента (\textbf{1} для \textbf{H}, \textbf{2} для \textbf{O}, \textbf{3} для \textbf{N} и \textbf{4} для \textbf{C},
\item пустые клетки ни с чем не соединены, и
\item хотя бы в одной клетке нарисован какой-то символ.
\end{itemize}
\InputFile
Первая строка входного файла содержит два натуральных числа \textbf{n} и \textbf{m} (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{50}) - размеры листочка, на котором рисует Серёжа. Далее следуют \textbf{n} строк по \textbf{m} символов в каждой, задающих конфигурацию химических элементов, которую нарисовал Серёжа; пустые клетки задаются символом "\textbf{.}".
\OutputFile
В выходной файл выведите одно слово: \textbf{Valid}, если линии провести требуемым образом можно, и \textbf{Invalid}, если нельзя.
Входные данные #1
3 4 HOH. NCOH OO..
Выходные данные #1
Valid