题目描述

给定一张 \(n\) 个点 \(m\) 条边的无向图，每条边上标有左括号 "("，或者右括号")"。

我们定义满足以下条件的字符串为括号串。

1.空串是括号串。

2.如果 \(A\) 是括号串，则 \(\big(A\big)\) 是括号串。

3.如果 \(A, B\) 都是括号串，则 \(AB\) 是括号串。

我们定义一条括号路径满足以下条件：从起点到终点经过的所有边上标的括号按经过的先后顺序写下来，构成的字符串是括号串。

有 \(q\) 组询问，每次询问起点为 \(x\)，终点为 \(y\) 的最短括号路径的长度，如果不联通，或者不存在合法路径则输出 \(-1\)。

输入格式

第一行输入三个整数 \(n, m, q\)。

接下来 \(m\) 行，每行两个整数和一个字符： \(u_i, v_i, c_i\)，表示一条连接节点 \(u_i\) 和 \(v_i\) 的无向边（ \(u_i \neq v_i\)），上面标记的括号为 \(c_i \in \{"(", ")"\}\)。

接下来 \(q\) 行，每行两个整数 \(x, y\)，表示一组询问的起点和终点。

\(1 \le n \le 400, 1 \le m \le 800, 1 \le q \le 10^5\)。

图可能存在重边，可能不连通，不会出现自环。

输出格式

输出 \(q\) 行，每行一个整数表示对应询问的答案。

样例输入

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

样例输出

0
2
4
2
6
-1
-1