A finite state machine with a stack is a machine that operates simultaneously on a graph and a stack. The graph describes the transitions of the machine. The vertices of the graph are called states. The edges are labeled with a letter of the English alphabet and an action. The action tells what to do with the stack when this edge is traversed. Possible actions are: push x – puts the letter x on the stack; pop – removes a letter from the top of the stack; poppush x – removes the letter from the top of the stack and puts the letter x on the stack. Initially, the machine is in state s0 and there is a word t on the stack. What is the shortest path that leads to clearing the stack? Input The first line of input contains three integers n, m and s0 (1 ≤ n ≤ 100, 0 ≤ m ≤ 500, 1 ≤ s0 ≤ n) denoting the number of states, transitions of the automaton and the number of the initial state. The states of the automaton are numbered with integers from 1 to n. The second line contains a string of lower-case English letters—the letters on the initial stack, in order from the bottom of the stack. Initially, there are at most 100 letters on the stack. The next m lines contain transition descriptions. Each transition is described by four tokens u, v, c, a, and means a transition from state u to state v available only when the letter c is at the top of the stack and when passing this transition, action a is performed. Follow the example test. Output Output NO if the stack cannot be emptied. Otherwise, output a single integer representing the number of passes needed to get it right. Examples: Input 6 7 1 aba 1 2 a pop 2 3 b poppush a 3 4 a pop 3 5 a pop 5 4 a push c 4 6 c pop 6 1 a pop Output 6

Input 3 3 1 a 1 2 a poppush b 2 3 b poppush c 3 1 c poppush a Output NO

Can anyone help me with this problem and say how to solve this optimally?