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 ui to vertex vi. 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:
- Vu: Determine the length of the shortest path from s to t without passing through vertex u.
- Ei: 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≤s,t≤n≤105,m≤5×105).
- The next m lines, where the i-th line contains two integers ui and vi.
- The next line contains a positive integer Q≤6×105.
- 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≤10, with only queries of type V.
- 25% of tests have a shortest path from s to t through ≤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:
9111912233775144556488669696V4V5V6E11E2E5
Output:
64−1446
