[HAOI2011]问题C

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 c.in 输出文件 c.out


题目描述:

n个人安排座位,先给每个人一个1~n的编号,设第i个人的编号为ai(不同人的编号可以相同),接着从第一个人开始,大家依次入座,第i个人来了以后尝试坐到ai,如果ai被占据了,就尝试ai+1ai+1也被占据了的话就尝试ai+2,……,如果一直尝试到第n个都不行,该安排方案就不合法。然而有m个人的编号已经确定(他们或许贿赂了你的上司...),你只能安排剩下的人的编号,求有多少种合法的安排方案。由于答案可能很大,只需输出其除以M后的余数即可。


输入格式:

第一行一个整数T,表示数据组数

对于每组数据,第一行有三个整数,分别表示nmM

m不为0,则接下来一行有m对整数,p1q1p2q2 ,…, pmqm,其中第i对整数piqi表示第pi个人的编号必须为qi


输出格式:

对于每组数据输出一行,若是有解则输出YES,后跟一个整数表示方案数mod M,注意,YES和数之间只有一个空格,否则输出NO


样例输入:

2

4 3 10

1 2 2 1 3 1

10 3 8882

7 9 2 9 5 10


样例输出:

YES 4

NO


数据范围:

30%的数据满足:1≤n≤10

100%的数据满足:1≤T≤101≤n≤3000≤m≤n2≤M≤1091≤piqi≤n 且保证pi互不相同。