Traders are not able to turn their carts around because of the narrowness of
the lane. Your job as a warden is to assign traders to locations in the lane.
The local merchants are all members of the town's merchant guild and are privileged
in that each of them gets assigned to his favourite location, whereas the
foreign traders have to accept any spot you assign to them.
Given all local trader's desired locations, you have to decide whether there
exists a valid assignment of foreign traders to locations in the lane such that
every trader (both foreign and local) is able to find a free spot. If this is
the case, you also have to find the number of different valid assignments
modulo a given integer
.
Example: Assume there are four traders. The first three traders in the queue are local traders with favourite positions 2, 1 and 1 respectively. The last trader is a foreign one. Every merchant finds a free spot in the following four cases:
where e.g. means that the first trader heads to position 2 first,..., and the last trader heads to position 3.
This example (which is the first test case of the sample input) shows that different local traders might have the same favourite location, that it is valid to assign a foreign trader to a spot that is desired by a local merchant and that a local merchant's final spot might not even be close to his favourite one.
Input
The first line contains the number of test cases.
Each test case starts with a line with three integer numbers
,
, and
(
),
where
is the number of local merchants among all
traders.
The next line contains exactly
pairs of integers
with
and all
different,
where
is the position of the
-th local trader in the queue
and
gives his favourite position.
If there are no local traders, this line is empty.
Output
For each test case, output a single line, containing NO, if it is
impossible that every merchant gets a free spot, or YES followed by
the number of different assignments modulo
(separated by a single space).
Sample Input
10 3 8882
7 9 2 9 5 10
Sample Output