분자, 분자

유기 분자는 놀랄 만큼 복잡해질 수 있어서, 특히 3차원 구조까지 자세히 그리려면 다양한 모양과 표기법이 필요하다. 하지만 원자 사이가 모두 단일 결합인 비교적 간단한 화합물로 범위를 좁히면, 결합이 모두 가로나 세로를 향하는 직사각형 격자 위에 분자를 그릴 수 있다. 이런 분자에서 탄소는 이웃한 원자 4개, 질소는 3개, 산소는 2개, 수소는 1개와 결합한다.

결합은 가로나 세로로 맞닿은 두 칸의 원자 사이에만 생기고, 같은 두 원자는 많아야 한 번 결합한다. 맞닿았다고 해서 반드시 결합하지는 않는다. 따라서 격자가 올바른 분자를 나타낸다는 말은, 모든 원자가 자기 결합 수를 정확히 채우도록 결합을 고를 수 있다는 뜻이다.

모든 격자가 올바른 분자가 되지는 않는다. 주어진 격자가 올바른 분자를 나타내는지 판정하는 프로그램을 작성하시오.

입력은 격자로 그린 분자 후보 여러 개로 이루어진다. 각 후보의 첫 줄에는 뒤따르는 직사각형의 행 수와 열 수를 나타내는 두 정수 r와 c가 주어진다 ($1 \le r, c \le 5$). 다음 r개 줄에는 각각 c개의 문자가 주어지고, 각 문자는 .(빈칸), H(수소), O(산소), N(질소), C(탄소) 중 하나다. 입력은 0이 두 개 있는 줄로 끝난다.

올바르다고 판정한 분자가 실제로 존재할 수 있는 물질은 아닐 수 있고, 한 격자 안에 분자가 둘 이상 들어 있을 수도 있다.

분자 후보마다 다음 두 줄 중 하나를 출력한다.

Molecule <num> is valid.
Molecule <num> is invalid.

여기서 <num>은 1부터 시작하는 일련번호다.