Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Reset Sequence
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 1001Accepted: 368Special Judge


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 ≤ δijn − 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 (“*”).

Sample Input

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

Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator