분자, 분자 2

유기 분자는 놀랄 만큼 복잡해질 수 있고, 특히 3차원 구조까지 나타내려면 다양한 모양과 표기법이 필요하다. 하지만 원자 사이의 결합이 모두 단일 결합인 비교적 단순한 화합물로 범위를 좁히면, 결합을 가로나 세로로 놓아 단순한 직사각형 격자 위에 나타낼 수 있다. 이런 분자에서 탄소는 인접한 원자 4개와, 질소는 3개와, 산소는 2개와, 수소는 1개와 결합한다. 모든 격자가 올바른 분자를 나타내지는 않는다. 주어진 격자가 올바른 분자를 나타내는지 판정하는 프로그램을 작성하라.

원자는 상하좌우로 맞닿은 원자와만 결합하고, 맞닿아 있다고 해서 반드시 결합하지는 않는다. 격자에 놓인 원자가 모두 필요한 결합 수를 정확히 채우도록 결합을 고를 수 있으면 그 격자는 올바르다.

입력은 격자로 그린 분자 후보 여러 개로 이루어진다. 각 분자의 첫 줄에는 뒤따르는 직사각형의 행 수와 열 수를 나타내는 두 정수 $r$과 $c$가 주어진다 ($1 \le r, c \le 20$). 다음 $r$개 줄에는 각각 문자 $c$개가 주어지고, 각 문자는 '.'(빈칸), 'H'(수소), 'O'(산소), 'N'(질소), 'C'(탄소) 중 하나이다. 입력은 0이 두 개 있는 줄 0 0으로 끝난다. 올바르다고 판정한 분자가 실제로 존재할 수 있는 물질일 필요는 없고, 격자 하나에 분자가 둘 이상 들어 있기도 하다.

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

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

<num>은 1부터 시작해 하나씩 늘어나는 번호이다.