아름다운 오토마타

Oleksandr은 문자열을 좋아한다. 그가 가장 좋아하는 자료구조는 접미사 오토마타(suffix automaton)이다.

소문자 영어 알파벳으로 이루어진 문자열 $s$를 생각하자. $s$의 접미사 오토마타는 각 간선 $e$에 문자 $l(e)$가 적혀 있고 시작 정점 $v_0$가 고정된 방향 비순환 그래프 $G$ 중에서 정점 수가 가장 적은 그래프이며, 다음 조건을 만족한다.

$\{w \mid w \text{는 } s\text{의 부분 문자열이다}\} = \{l(e_1)l(e_2)\cdots l(e_k) \mid (e_1, e_2, \ldots, e_k) \text{는 } v_0\text{에서 시작하는 } G\text{의 경로이다}\}$

Oleksandr은 다른 어떤 그래프보다 접미사 오토마타를 더 좋아한다. 방향 비순환 그래프 $G$의 각 간선에 소문자를 적고 시작 정점 $v_0$를 골랐을 때 $G$가 $s$의 접미사 오토마타가 될 수 있으면, 그는 $G$를 $s$-beautiful하다고 부른다.

Oleksandr은 사전순으로 작은 문자열을 좋아한다. 주어진 그래프 $G$에 대해, $G$가 $s$-beautiful하도록 하는 사전순으로 가장 작은 문자열 $s$를 구하라.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($1 \le n \le 2000$, $1 \le m \le 3000$). 이어지는 $m$개의 줄에는 $v$에서 $u$로 향하는 방향 간선을 나타내는 두 정수 $v$, $u$가 한 줄에 하나씩 주어진다 ($1 \le v, u \le n$, $v \ne u$). 그래프 $G$는 비순환임이 보장된다.

$G$가 $s$-beautiful하도록 하는, 사전순으로 가장 작은 소문자 문자열 $s$를 한 줄에 출력한다. 그런 문자열이 없으면 $-1$을 출력한다.

처음 세 예제에 대한 접미사 오토마타는 아래와 같다.