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