Routing Scheme Decomposition in Nearly Acyclic Networks

Consider a network consisting of (N) nodes numbered from (1) to (N). Each node is designated as a sender, a receiver, or neither. The number of senders is equal to the number of receivers, and we denote this number by (S) (with (S \ge 1)).

The connectivity of the network is described by a collection of directed edges. Each edge is represented as (i \to j), meaning node (i) can directly route to node (j). All edges satisfy (i<j) except for exactly (K) edges (with (0 \le K \le 2)) that satisfy (i>j). There are no self-loops (i.e. no edge of the form (i \to i)).

A routing scheme is a description consisting of (S) directed paths from senders to receivers, with no two paths sharing the same start and end pair. In other words, the paths connect distinct senders to distinct receivers. A path from sender (s) to receiver (r) is given by a sequence of nodes: [ s = v_0 \to v_1 \to v_2 \to \cdots \to v_e = r, ] where for every (0 \le i < e), the directed edge (v_i \to v_{i+1}) exists in the network. Note that a node may appear more than once in the same path.

The task is to compute the number of routing schemes such that every directed edge in the network is used exactly once. Since the answer might be very large, output the result modulo (10^9+7).

It is guaranteed that there is at least one valid routing scheme for each test case.

inputFormat

The input begins with an integer \(T\) (\(1 \le T \le \text{some limit}\)) denoting the number of test cases. Each test case has the following format:

1. The first line contains three integers: \(N\) (the number of nodes), \(S\) (the number of senders, which is also the number of receivers), and \(M\) (the number of directed edges).
2. The second line contains \(S\) distinct integers indicating the indices of the senders.
3. The third line contains \(S\) distinct integers indicating the indices of the receivers.
4. The next \(M\) lines each contain two integers \(u\) and \(v\) representing a directed edge from node \(u\) to node \(v\). It is guaranteed that all edges satisfy \(uv\), and there are no self-loops.

The input guarantees that the network has an Eulerian-like structure (for each sender \(s\), \(\text{outdeg}(s) - \text{indeg}(s)=1\), for each receiver \(r\), \(\text{indeg}(r) - \text{outdeg}(r)=1\), and every other node is balanced, i.e. \(\text{indeg}=\text{outdeg}\)).

outputFormat

For each test case, output a single integer: the number of valid routing schemes modulo \(10^9+7\).

sample

3
3 1 2
1
3
1 2
2 3

1