Suffix automaton
A suffix automaton for a string **w** is a deterministic finite automaton **A** that recognizes the language **Suff(w)**, which is the set of all suffixes of the word **w**. For instance, the suffix automaton for the word **abbab** should accept exactly these words: {**abbab**, **bbab**, **bab**, **ab**, **b**, **ε**}. 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 **w**, and also determine this word. For simplicity, assume the alphabet size is unlimited, and you can use numbers from **1** to **k** as symbols (you can choose **k**).
Input
The first line of the input contains three integers: **n**, **m**, and **t** - the number of states, the number of transitions, and the number of acceptable states, respectively (2 ≤ **n** ≤ 200, 1 ≤ **m** ≤ 1000, 1 ≤ **t** ≤ **n**). The second line contains **t** integers, representing the numbers of the acceptable states (states are numbered starting from **1**, with the initial state being **1**).
The next **m** lines describe the transitions: each line contains two integers **s_i** and **t_i**, indicating a transition from **s_i** to **t_i**.
Output
In the first line of the output, print two integers **l** and **k** - the length of the word **w** and the size of the alphabet. Use numbers {**1**, ..., **k**} as elements of the alphabet. **k** should not exceed **m**.
The second line should contain **l** integers representing the word **w**.
The third line should contain **m** 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.
**Note**
