## NOI '21 P2 - Intersecting Paths

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem type

There is a directed graph such that the vertices may be partitioned into levels. The -th level has vertices, and the number of vertices in level and level are the same (i.e. ), and for the -th level , we have . Edges whose tails are vertices in level  will only go to vertices in level . There are no edges whose heads are vertices in level , and there are no edges whose tails are vertices in level .

Now we want to choose a set of paths with paths in the set. Each path in the set starts from a vertex in level and ends in a vertex in level , and a vertex in the graph may only occur in one path. More formally, if we number the vertices in each level by , then each path may be written as a -tuple denoting that the path passes through vertex  in level , and there exists an edge connecting vertex in level  to vertex in level .

If we draw the paths on paper, we know they will produce some intersections. For paths , suppose the edges between level and level in the paths are and , then if , we say the two paths produce an intersection in level . The number of intersections of two paths is the sum of number of intersections they produce in level . For a set of paths, the number of intersections is defined to be sum of number of intersections between two different paths. In the following example, there are 3 paths producing 3 intersections in total. The red dots are the intersections: Now we want to compute the difference between the number of sets of paths with even number of intersections and the number of sets of paths with odd number of intersections. Two sets of paths are considered to be the same if and only if the -tuple corresponding to the paths are the same. Since the final result might be large, please output the answer modulo , a prime.

#### Input Specification

There are multiple test cases in one test set. The first line is an integer denoting the number of test cases.

For each test case, the first line is an integer denoting there are levels of vertices.

The second line contains intergers denoting the number of vertices in each level. It is guaranteed that and for .

The third line contains integers denoting the number of edges between vertices in level and vertices in level . It is guaranteed that .

There are sections of input following. The -th section contains lines. Each line contains two integers denoting vertex in level has an edge whose head is vertex in level .

It is guaranteed there are no parallel edges.

#### Output Specification

The output has lines. Each line contains an integer denoting the answer (the number of sets of paths with even number of intersections minus the number of sets of paths with odd number of intersections) modulo .

#### Samples Input 1

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

#### Sample Output 1

1

#### Explanation for Sample Output 1

There are two sets of paths with even number of intersections and one with odd number of intersections, so the output is 1.

In set 1, the two paths are and in the -tuple notation. There is one intersection in total. Notice if we swap the two paths, we obtain the same set of paths, and we do not count the same set twice.

In set 2, the two paths are and . There are 2 intersections.

In set 3, the two paths are and . There are 0 intersections.

Sample inputs and outputs can be found here.

#### Constraints

For all test sets, , , . It is guaranteed in each test set there will be at most one test case with in each test set.

Test Case  Additional constraints
1~4 2 10 None.
5~6 10 A,B
7~8 A
9~10 None.
11~13 2 100
14~15 100 A,B
16~17 A
18~20 None.

Additional constraint A: For all  , .
Additional constraint B: There is at most one set of paths.