You are a warden of a small town’s merchant guild. Early this morning, a number of local and foreign traders (numbered from 1 to n) line up in a row in order to enter the town’s market lane. There are n locations along the lane where the merchants can place their carts and sell their goods. Beginning with the merchant #1, each merchant, one after the other, enters the lane with his cart, heads it to his assigned location, and, if it is free, occupies it. Otherwise he continues to the next free spot and occupies it. If all succeeding locations are occupied, he leaves without selling goods. 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 M. 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: (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 1, 3), (2, 1, 1, 4) where e.g. (2, 1, 1, 3) 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 n, m, and M (1 ≤ n ≤ 300,0 ≤ m ≤ n,2 ≤ M ≤ 109), where m is the number of local merchants among all n traders. The next line contains exactly m pairs of integers a1, b1, . . . , am, bm with 1 ≤ ai, bi ≤ n and all ai different, where ai is the position of the i-th local trader in the queue and bi 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 M (separated by a single space). Sample Input 4 4 3 10 122131 6 3 987654321 123456 18 0 100769
2/2 10 3 8882 7 9 2 9 5 10 Sample Output YES 4 YES 49 YES 68184 NO