Let $G$ be a directed acyclic graph with $n$ vertices numbered from $1$ to $n$ and $m$ edges numbered from $1$ to $m$. Edge number $i$ connects vertex $u_i$ to vertex $v_i$. Between two vertices, there may be multiple connecting edges. Given two vertices $s$ and $t$ on the graph. The length of a path is defined as the number of edges on that path.
You need to answer $Q$ queries, each falling into one of two types:
- `V u`: Determine the length of the shortest path from $s$ to $t$ without passing through vertex $u$.
- `E i`: Determine the length of the shortest path from $s$ to $t$ without passing through edge $i$.
### Input
- The first line contains four positive integers $n, m, s,$ and $t$ $(1 \le s, t \le n \le 10^5, m \le 5 \times 10^5)$.
- The next $m$ lines, where the $i$-th line contains two integers $u_i$ and $v_i$.
- The next line contains a positive integer $Q \le 6 \times 10^5$.
- The next $Q$ lines, each consisting of a character `V` or `E`, followed by an integer corresponding to the described query.
### Output
- For each query, print an integer on a separate line, representing the answer to that query. If there is no path satisfying the query requirements, print `-1` on that line.
### Constraints
- 25% of tests have $Q \le 10$, with only queries of type `V`.
- 25% of tests have a shortest path from $s$ to $t$ through $\le 200$ edges, with only queries of type `V`.
- 25% of tests have only queries of type `V`.
- The remaining 25% of tests have no additional constraints.
### Example
Input:
```
9 11 1 9
1 2
2 3
3 7
7 5
1 4
4 5
5 6
4 8
8 6
6 9
6 9
6
V 4
V 5
V 6
E 11
E 2
E 5
```
Output:
```
6
4
-1
4
4
6
```
