Intermediate vertices X34137

Given a directed graph and two different vertices u and v, compute how many vertices x different from u and v there are such that there exists some path from u to v passing through x.

Input

The input consists in several cases. Each case begins with n, u, v and m, followed by m different pairs x y, with x ≠ y, which indicate an arc that goes from x to y. Assume 2 ≤ n ≤ 10⁴, 0 ≤ m ≤ 10n, and that the vertices are numbered between 0 and n − 1.

Output

For each case, write the number of vertices that can be visited when going from u to v following some path.

Hint

For each case, essentially the expected solution only makes two traversals, each on the right graph.