#P3609. Reset Sequence

    ID: 2619 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>POJ Founder Monthly Contest – 2008.06.29, frkstyc

Reset Sequence

Description

A reset sequence is a series of commands which, when issued, brings a chip to the ready state. When a chip is powered on or encounters an error, it may be in an arbitrary state. The reset sequence ensures that the chip is appropriately (re-)initialized for subsequent tasks.

The state control of a chip is typically modeled after a finite automaton. (Please refer to Problem 3599 Pumping Lemma for an informal description of finite automata.) When it receives a command, the chip transits from its current state to another state as its control logic dictates.

Given the description of the control logic of a chip, compute the shortest reset sequence.

Input

The input consists of a single test case. The first line contains two integers n and m (2 ≤ n ≤ 8, 1 ≤ m ≤ 16), which are the numbers of states and different commands. The states are numbered 0 through n − 1. State 0 is the only ready state. The commands are denoted by hexadecimal digits 0 through f.

Immediately following the first line comes an n × m matrix Δ = {δij}n×m with zero-based indices. Each element δij (0 ≤ δijn − 1) indicates that when the chip receives command j in state i, it transits to state δij .

Output

Output the shortest reset sequence using its representation by hexadecimal digits. If there are multiple such sequences, output any one. If there are no such sequences, output an asterisk (“*”).

3 4
2 1 1 2
1 0 0 0
0 0 0 1
101

Source

POJ Founder Monthly Contest – 2008.06.29, frkstyc