Safe Bridge Tour

In the Pantanal wetland, a tourist attraction is built with stone piers connected by stone bridges. Each bridge connects two distinct piers and there is at most one bridge between any pair of piers. However, dangerous piranhas patrol the pond. Each piranha moves along a fixed cyclic route with a period of either \(2\), \(3\) or \(4\) time units. Specifically, if a piranha has cycle length \(p\) and its cycle is given by the sequence \(a_1,a_2,\dots,a_p\), then at each time unit \(t\ge1\) it moves such that its position is \(a_{((t-1)\bmod p)+1}\) (with indices starting at 1).

Mr. Dodo, a thrill-seeker, wants to travel from a designated Start pier \(S\) to an End pier \(E\) in exactly \(K\) time units. He must move along a bridge every time unit (i.e. he cannot stay at the same pier). If he and any piranha arrive at the same pier at the same time, the piranha will attack.

Your task is to count the number of safe routes that Mr. Dodo can take from \(S\) to \(E\) in exactly \(K\) time units, without ever arriving at a pier at the same time as a piranha.

Note in mathematical terms:
Let \(G\) be an undirected graph with \(N\) vertices (piers) and \(M\) edges (bridges). There are \(P\) piranhas. For each 1 ≤ t ≤ K, a vertex \(v\) is dangerous if at least one piranha is scheduled to be there at time \(t\). Mr. Dodo’s route \(v_0=S, v_1, v_2, \dots, v_K=E\) is safe if for every time \(t=1,2,\dots,K\), vertex \(v_t\) is not dangerous. Count the total number of safe routes.

inputFormat

The input consists of several parts:

1. The first line contains three integers: N, M, and K — the number of piers, the number of bridges, and the total travel time (in time units), respectively.
2. The second line contains two integers: S and E (1-indexed), representing the starting and ending piers.
3. The next M lines each contain two integers u and v, indicating that there is a bidirectional bridge between piers u and v.
4. The following line contains an integer P, the number of piranhas.
5. Each of the next P lines describes one piranha. Each line starts with an integer p (which is either 2, 3, or 4, indicating the period of the piranha), followed by p integers representing the piranha's cyclic route. For a piranha with cycle \(p\) and route \(a_1,a_2,\dots,a_p\), its position at time t (for \(t \ge 1\)) is \(a_{((t-1) \bmod p)+1}\).

outputFormat

Output a single integer — the number of safe routes from pier S to pier E in exactly K time units.

sample

3 3 2
1 3
1 2
2 3
1 3
1
2 2 3

0