Bracket Path

A bracket symbol is one of the eight characters (, ), [, ], {, }, <, >. A string made only of bracket symbols is a correct bracket expression when both of the following hold:

• every left bracket has a matching right bracket of the same kind, and every right bracket is matched;
• no two pairs of matching brackets cross. Any two such pairs are either disjoint, or one pair lies entirely inside the other.

For example, ([])<> is a correct bracket expression, while <{>} is not, because the curly pair and the angle pair cross each other.

You are given a directed graph with $n$ vertices. Every edge carries one bracket symbol. A path is valid when the symbols on its edges, read in order, form a correct bracket expression. Find the length of a shortest valid path from vertex $s$ to vertex $t$. The path may pass through the same vertex several times. The length of a path is the number of edges on it.

The empty path uses no edges, and the empty string is a correct bracket expression, so the answer is $0$ when $s$ equals $t$.

The first line contains four integers $n$, $m$, $s$, $t$ ($1 \leq n \leq 200$, $0 \leq m \leq 2000$, $1 \leq s, t \leq n$): the number of vertices, the number of edges, the starting vertex, and the ending vertex.

Each of the next $m$ lines contains two integers $x$, $y$ and a bracket symbol $b$ ($1 \leq x, y \leq n$), describing an edge from vertex $x$ to vertex $y$ labeled with $b$. The graph may contain loops and multiple edges.

Print one line with one integer, the length of the shortest valid path from $s$ to $t$. If no such path exists, print $-1$. If a path exists, its length does not exceed $10^{18}$.