23517번 - Beautiful Automata 다국어

Oleksandr is a fan of strings. His favourite data structure is suffix automaton.

Consider a string $s$ of lowercase English letters. The suffix automaton of $s$ is the smallest (having the smallest number of vertices) directed acyclic graph $G$ with a letter $l(e)$ written on each edge $e$ and a fixed starting vertex $v_0$ such that $$\{w\, |\, w \text{ is a substring of } s\} = \{l(e_1)l(e_2)...l(e_k)\, |\, (e_1, e_2, ..., e_k) \text{ is a path in } G \text{ starting at } v_0\}\text{.}$$

Oleksandr likes suffix automata more than any other graphs. He calls a directed acyclic graph $G$ $s$-beautiful if it is possible to write a lowercase English letter on each edge and choose a starting vertex $v_0$ so that $G$ will become a suffix automaton of the string $s$. Oleksandr likes lexicographically small strings, so please help him find for a given graph $G$ the lexicographically smallest string $s$ such that $G$ is $s$-beautiful.

The first line contains two integers $n$ and $m$ ($1 \le n \le 2000$, $1 \le m \le 3000$), the number of vertices and the number of edges in $G$ respectively. Each of the next $m$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$, $v \ne u$), denoting a directed edge from $v$ to $u$. It is guaranteed that $G$ is acyclic.

Output a single line containing the lexicographically smallest string $s$ consisting of lowercase English letters such that $G$ is $s$-beautiful. If such string does not exist, output $-1$.

Suffix automata for the first three sample tests are shown below: