Shortest Balanced Walk

問題文

頂点に $1$ から $N$ までの番号がついた $N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいて、ラベル $c_i$ が付与されています。 ここで、 $c_i$ は ( または ) です。

頂点 $1$ を始点、頂点 $N$ を終点とするウォークのうち、通過した辺のラベルを通過順に並べた文字列が正しいかっこ列であるようなものを、 良いウォーク と呼びます。

良いウォークが存在するか判定してください。

存在する場合は、良いウォークの長さとしてありえる値の最小値を求めてください。

制約

• $2 \leq N \leq 200$
• $N-1 \leq M \leq \min \Big( \frac{N(N-1)}{2}, 200 \Big)$
• $N, M$ は整数
• $1 \leq u_i < v_i \leq N$
• $u_i, v_i$ は整数
• $c_i$ は ( または )
• 与えられるグラフは単純連結無向グラフ

入力

入力は以下の形式で標準入力から与えられる。

出力

良いウォークが存在する場合は、その長さとしてあり得る値の最小値を出力してください。

存在しない場合は、 -1 を出力してください。

サンプル 1

入力

6 6
1 2 (
1 3 )
2 3 )
3 4 (
3 5 )
5 6 )

出力

6

頂点を $1 \to 2 \to 3 \to 4 \to 3 \to 5 \to 6$ の順にたどるウォークは、通過した辺のラベルを辺の通過順に並べると ()(()) になるため、良いウォークです。長さが $6$ 未満の良いウォークは存在しないため、 $6$ が答えです。

ウォークでは同じ頂点や同じ辺を複数回通っても良いことに注意してください。

サンプル 2

入力

6 6
1 2 (
1 3 )
2 3 )
3 4 )
3 5 (
4 6 (

出力

-1

良いウォークは存在しません。

サンプル 3

入力

6 5
1 2 (
1 3 )
3 4 )
4 5 )
5 6 )

出力

8