tjoi2012 图同构

内存限制：128 MiB 时间限制：10 Sec

两个图同构的判定问题目前还没有高效的算法。不过有这样一种方法，如果两个图，度为0的点的个数

相同，度为1的点的个数相同，度为2的点的个数相同……那么就认为两个图同构，但是这样一种方法并非总

是正确的。现要求出，n个点，每个点的度不超过K，没有自环的图被上述算法分为了多少种。

第一行，一个整数T

接下来T行，每行两个整数n，k

T行，在n和k的限制下，有多少种图，由于此数可能过大，输出其对1，000，000，009的余数

对应n-3，k-2有

V={I，2，3)

E={),{(1,2)),{(1,2),(1,2)),{(1,2),(2,3)),{(1,2),(2,3),(1,3))

l<=n，k<= 1000，l<=t<=3

请不要提交，错误数据.求正确数据！

#4324. tjoi2012 图同构