当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
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.
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 ≤ δij ≤ n − 1) indicates that when the chip receives command j in state i, it transits to state δij .
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
| 时间上限 | 内存上限 |
| 1000 | 131072 |