Parade Route City Count

C Country is a prosperous nation consisting of \( n \) cities and \( m \) directed roads. The cities are numbered from 1 to \( n \). For any two cities \( x \) and \( y \), if there exists a sequence of roads from \( x \) to \( y \) we denote it as \( x \Rightarrow y \). The original roads satisfy the following property: for any three distinct cities \( x \), \( y \), and \( z \), if \( x \Rightarrow z \) and \( y \Rightarrow z \), then either \( x \Rightarrow y \) or \( y \Rightarrow x \).

There will be \( q \) parade plans. In the \( i\)-th parade, citizens plan to start at city \( s_i \) and, after visiting several cities (a city may be visited more than once), end at city \( t_i \). To make the parade more exciting, \( k \) (\( 0\le k\le 2 \)) additional directed roads are built temporarily for that parade (these extra roads do not need to satisfy the original property and are only available for that parade).

The task is: for each parade plan, determine how many cities may be visited along some valid route from \( s_i \) to \( t_i \). A city is considered visited if it appears at least once in the route. It can be shown that a city \( v \) can be incorporated into the parade route if and only if there exists a path from \( s_i \) to \( v \) and a path from \( v \) to \( t_i \) in the augmented graph.

Input: The first line contains two integers \( n \) and \( m \). The next \( m \) lines each contain two integers \( u \) and \( v \) denoting a directed road from city \( u \) to city \( v \). Then a line containing integer \( q \) is given. Each of the next queries begins with a line containing three integers \( s_i \), \( t_i \), and \( k \) (the number of extra temporary roads for this query). Each of the next \( k \) lines contains two integers \( u \) and \( v \) representing a temporary road from city \( u \) to city \( v \>.

Output: For each query, output a single integer indicating the maximum number of cities that may be visited in a parade from \( s_i \) to \( t_i \) (i.e. the number of cities \( v \) for which there exists a route from \( s_i \) to \( t_i \) that visits \( v \)).

inputFormat

The input begins with a line containing two integers \( n \) and \( m \), where \( n \) is the number of cities and \( m \) is the number of directed roads. The next \( m \) lines each contain two integers \( u \) and \( v \) indicating that there is a directed road from city \( u \) to city \( v \). Following that, there is an integer \( q \) denoting the number of parade queries. For each query, the first line contains three integers \( s_i \), \( t_i \), and \( k \) (\( 0 \le k \le 2 \)). Then follow \( k \) lines, each with two integers \( u \) and \( v \), representing a temporary road from city \( u \) to city \( v \) available only for that query.

outputFormat

For each query, print a single integer on a separate line, representing the maximum number of cities that can be visited along some parade route from \( s_i \) to \( t_i \) in the augmented graph (i.e. the number of cities \( v \) for which \( s_i \) can reach \( v \) and \( v \) can reach \( t_i \)).

sample

4 4
1 2
2 3
1 3
3 4
3
1 4 0
2 4 1
4 2
1 3 2
4 1
4 3

4
3
4