Suffix automaton#4164
A suffix automaton for a string is a deterministic finite automaton that recognizes the language Suff(w), which is the set of all suffixes of the word . For instance, the suffix automaton for the word abbab should accept exactly these words: \{\textbf{abbab}, \textbf{bbab}, \textbf{bab}, \textbf{ab}, \textbf{b}, \varepsilon\}. The automaton must have no unreachable states and no states from which an acceptable state cannot be reached. We do not require the automaton to be minimal.
The diagram illustrates the suffix automaton for the word abbab.
Given the skeleton of a suffix automaton for some word, your task is to reconstruct the suffix automaton. You are provided with the states, transitions, initial state, and acceptable states, but the labels on the edges are missing.
Your goal is to assign labels to the edges of the given suffix automaton so that it becomes the suffix automaton of some word , and also determine this word. For simplicity, assume the alphabet size is unlimited, and you can use numbers from to as symbols (you can choose ).
The first line of the input contains three integers: , , and — the number of states, the number of transitions, and the number of acceptable states, respectively (2 \le n \le 200, 1 \le m \le 1000, 1 \le t \le n). The second line contains integers, representing the numbers of the acceptable states (states are numbered starting from , with the initial state being ).
The next lines describe the transitions: each line contains two integers s_i and t_i, indicating a transition from s_i to t_i.
In the first line of the output, print two integers and — the length of the word and the size of the alphabet. Use numbers \{1, \ldots, k\} as elements of the alphabet. should not exceed .
The second line should contain integers representing the word .
The third line should contain integers, which are the labels for the transitions of the automaton skeleton, in the order they appear in the input.
It is guaranteed that a solution always exists.
Example 1
