9159: Pumping

Prerequisite: Deterministic Finite Automaton, DFA
A deterministic finite automaton (DFA) $M$ is a 5-tuple (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F)(Q,Σ,δ,q0,F), consisting of:

• a finite set of states $Q$
• a finite set of input symbols called the alphabet $\Sigma$
• a transition function δ: Q×Σ→Q\delta:\ Q\times \Sigma \rightarrow Qδ: Q×Σ→Q
• a start state q0∈Qq_{0}\in Qq0∈Q
• a set of accept states F⊆QF\subseteq QF⊆Q ($F$ is not empty)

Let s=c1c2⋯cns = c_1c_2\cdots c_ns=c1c2⋯cn be a string over the alphabet $\Sigma$. The automaton $M$ $\text{accepts}$ the string $s$ if a sequence of states, r0, r1, ⋯, rnr_0,\ r_1,\ \cdots,\ r_nr0, r1, ⋯, rn, exists in $Q$ with the following conditions:
In words, the first condition says that the machine starts in the start state q0q_0q0. The second condition says that given each character of string $s$, the machine will transition from state to state according to the transition function $\delta$. The last condition says that the machine $\text{accepts}$ $s$ if the last input of $s$ causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton $\text{rejects}$ the string - there is two cases where $M$ rejects the string:

• At some intermediate state rir_iri, there doesn't exists a transition of state rir_iri and character ci+1c_{i+1}ci+1, that is, (ri,ci+1)∉dom(δ)(r_i,c_{i+1})\notin dom(\delta)(ri,ci+1)∈/dom(δ).
• The final state is not an accept state, that is, rn∉Fr_n\notin Frn∈/F.

The set of strings that $M$ accepts is called the language recognized by $M$ and this language is denoted by L(M)L(M)L(M).

$\text{Problem}$

You are given a deterministic finite automaton $M$. We say a string s∈L(M)s\in L(M)s∈L(M) can be \textit{pumped} if the string can be divided into three parts s=xyzs=xyzs=xyz satisfying:

•  ∣y∣>0|y|>0∣y∣>0
•  for each $i\ge 0$, xyiz∈L(M)xy^iz\in L(M)xyiz∈L(M). Here yiy^iyi means repeating string $y$ for $i$ times.

Please find a string in L(M)L(M)L(M) that can be pumped or report it is impossible.

The first line contains three integers n, m, kn,~ m,~ kn, m, k (1≤n≤5×105, 0≤m≤106, 1≤k≤n1\le n\le 5\times 10^5,~ 0\le m\le 10^6,~1\le k\le n1≤n≤5×105, 0≤m≤106, 1≤k≤n), denoting the number of states, the number of transitions and the number of accept states in the DFA. We number the states in the DFA from $1$ to $n$, and let the start state be state $1$.
Then follows a line with $k$ distinct integers a1, a2, ⋯, aka_1,\ a_2,\ \cdots,\ a_ka1, a2, ⋯, ak (1≤ai≤n1\le a_i\le n1≤ai≤n), denoting the accept states.
Then follows $m$ lines, and each line contains three integers u, v, cu,~v,~cu, v, c (1≤u, v≤n1\le u,\ v\le n1≤u, v≤n, and $c$ is a lowercase character), denoting a transition δ(u,c)=v\delta(u, c)=vδ(u,c)=v in the DFA. It is guaranteed that there is at most one transition for each state $u$ and each character $c$.
Note that the input data size can be large, so if you use$\text{std::cin}$ in $\text{C++}$, you may need to call $\text{std::ios::sync\_with\_stdio(false); cin.tie(nullptr);}$ to disable stream synchronization.

Print a string of length up to $3n$ that can be pumped. If there are multiple answers, print any. If there is no answer, print $-1$ instead.
It can be proved that if answer exists, then at least one answer has length $3n$ or less.

7 9 1
3
1 2 a
2 5 c
5 2 d
5 7 b
5 3 a
4 2 b
2 3 a
3 3 e
3 6 a

acdca