Задача H. Пароли

Софтуерната фирма ABC (Aytos-Burgas Computers) разработила система за достъп, основана на числови пароли, разпознавани от детерминиран краен автомат:

• автоматът има N състояния, означени с 0, 1, …, N-1, където 2 <= N  <= 1000. При започване на работа автоматът винаги се намира в състояние 0, наричано начално. Част от състоянията на автомата са заключителни, останалите са незаключителни. Началното състояние не може да бъде заключително.

• входната азбука на автомата се състои от цифрите 1, …, M където 2 <= M <= 9.

• автоматът работи в дискретни тактове, като чете по една цифра на такт.

• на всяка стъпка автоматът чете цифра a от входа и използвайки текущото състояние q изчислява следващото състояние q' =d (q,a), където dе функция, дефинирана за всяка двойка (q,a), q = 0, 1,…, N-1, a=1, 2, …, M .

• автоматът спира, когато и последната цифра на входа е прочетена. Ако в този момент автоматът е в заключително състояние, входното число се разпознава, в противен случай числото не се разпознава.

Да се направи програма PASS.EXE, която намира най-малкото число, разпознавано от автомата.

Първият ред на входния файл PASS.INP съдържа числата N и M, разделени с интервал. Всеки от следващите N реда задава стойностите на dза състоянията 0, 1, …, N-1 в указания ред. За всяко състояние q, съответния ред съдържа M числа, разделени с по един интервал – стойностите на d(q,а) за a = 1, …, М. Последният ред на входния файл съдържа броя и номерата на заключителните състояния, разделени с по един интервал.

В изходния файл PASS.OUT е записано най-малкото число, което се разпознава от автомата. Ако числото има много цифри да се изведе на отделни редове, като се раздели на групи по 50 цифри. Ако автоматът не разпознава нито едно число, в изходния файл да се запише числото 0.

ПРИМЕР:

PASS.INP                      PASS.OUT
6 2              122
1 5
1 2
2 3
3 2
4 3
4 0
1 3