괄호 경로

괄호 문자는 (, ), [, ], {, }, <, > 여덟 개 중 하나다. 괄호 문자로만 이루어진 문자열이 다음 두 조건을 만족하면 올바른 괄호 식이라고 한다.

• 모든 여는 괄호는 같은 종류의 닫는 괄호와 짝을 이루고, 모든 닫는 괄호도 짝이 있다.
• 짝을 이루는 두 괄호 쌍은 교차하지 않는다. 두 쌍은 서로 떨어져 있거나, 한 쌍이 다른 쌍 안에 완전히 들어 있다.

예를 들어 ([])<> 는 올바른 괄호 식이지만, <{>} 는 중괄호 쌍과 꺾쇠 괄호 쌍이 교차하므로 올바르지 않다.

정점이 $n$개인 방향 그래프가 주어진다. 각 간선에는 괄호 문자가 하나씩 적혀 있다. 어떤 경로가 지나는 간선의 문자를 순서대로 이어 붙인 문자열이 올바른 괄호 식이면 그 경로를 올바른 경로라고 한다. 정점 $s$에서 정점 $t$까지 가는 가장 짧은 올바른 경로의 길이를 구하라. 경로는 같은 정점을 여러 번 지나도 된다. 경로의 길이는 지나는 간선의 개수다.

간선을 하나도 지나지 않는 빈 경로도 올바른 괄호 식이므로, $s$와 $t$가 같으면 답은 $0$이다.

첫째 줄에 정수 $n$, $m$, $s$, $t$가 주어진다 ($1 \leq n \leq 200$, $0 \leq m \leq 2000$, $1 \leq s, t \leq n$). 차례대로 정점 개수, 간선 개수, 시작 정점, 도착 정점이다.

다음 $m$개 줄에는 각각 정수 $x$, $y$와 괄호 문자 $b$가 주어진다 ($1 \leq x, y \leq n$). 정점 $x$에서 정점 $y$로 가는 간선에 문자 $b$가 적혀 있다는 뜻이다. 자기 자신으로 돌아오는 간선이나 같은 두 정점을 잇는 간선이 여러 개 있을 수 있다.

$s$에서 $t$까지 가는 가장 짧은 올바른 경로의 길이를 한 줄에 출력한다. 그런 경로가 없으면 $-1$을 출력한다. 경로가 존재한다면 그 길이는 $10^{18}$을 넘지 않는다.