Beautiful Automata

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

Consider a string $s$ of lowercase English letters. The suffix automaton of $s$ is the smallest directed acyclic graph $G$ (the one with the fewest vertices) with a letter $l(e)$ written on each edge $e$ and a fixed starting vertex $v_0$, such that

$\{w \mid w \text{ is a substring of } s\} = \{l(e_1)l(e_2)\cdots l(e_k) \mid (e_1, e_2, \ldots, e_k) \text{ is a path in } G \text{ starting at } v_0\}.$

Oleksandr likes suffix automata more than any other graphs. He calls a directed acyclic graph $G$ $s$-beautiful if a lowercase letter can be written on each edge and a starting vertex $v_0$ chosen so that $G$ becomes the suffix automaton of $s$.

Oleksandr likes lexicographically small strings. Given a graph $G$, find 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$. 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 no such string exists, output $-1$.

The suffix automata for the first three sample tests are shown below.