问题 25342 --鳄鱼

25342: 鳄鱼

时间限制: 1 Sec  内存限制: 128 MB
提交: 25  解决: 12
[提交][状态][讨论版][命题人:]

题目描述

在观看完各种动物后,有一部分MM 由于没有看到自己喜欢的动物而很生气,她们把绝恋扔在一边自己去玩了,绝恋正在纠结,忽然听到MM 的呼救声,天赐良机!!

绝恋发现,MM 们被困在鳄鱼馆的角落里了,鳄鱼馆其实就是一个大池塘,中间建设了许多的石墩和石桥,且每两座石墩之间至多只有一座石桥。池塘中有许多鳄鱼。绝恋及时赶到鳄鱼馆营救MM,但也不敢拿自己的性命开玩笑,于是他开始了仔细的实地勘察,并得到了一些惊人的结论:鳄鱼的行进路线有周期性,这个周期只可能是23 或者4 个单位时间。每个单位时间里,鳄鱼可以从一个石墩游到另一个石墩。每到一个石墩,如果上面有人它就会实施攻击,否则继续它的周期运动。如果没有到石墩,它是不会攻击人的。

借助先进的仪器,绝恋很快就摸清了所有鳄鱼的运动规律,他要开始设计自己的行动路线了。每个单位时间里,他只可以沿着石桥从一个石墩走到另一个石墩,而不可以停在某座石墩上不动,因为站着不动还会有其它危险。如果绝恋和某条鳄鱼在同一时刻到达了某座石墩,就会遭到鳄鱼的袭击,他当然不希望发生这样的事情。

绝恋开始在start 石墩上,而MM 们被困在end 石墩上,绝恋要从start 出发,恰好经过Step 个单位时间后到达end 石墩,石墩可以重复经过(包括start nd),绝恋希望你能告诉他绝恋有多少条满足上述条件的路线,以便计算成功救出MM的几率。

输入

第一行包含五个正整数NMStartEnd Step,分别表示石墩数目、石桥数目、Start 石墩和End 石墩的编号和一条路线所需的单位时间。石墩用0 N1 的整数编号。

2 M + 1 行,给出石桥的相关信息。每行两个整数x y0 x, y N1,表示这座石桥连接着编号为x y 的两座石墩。

M + 2 行是一个整数NFish,表示鳄鱼的数目。

M + 3 M + 2 + NFish 行,每行给出一条鳄鱼的相关信息。每行的第一个整数是TT = 23 4,表示鳄鱼的运动周期。接下来有T 个数,表示一个周期内鳄鱼的行进路线。

输出

输出路线的种数,因为这个数可能很大,你只要输出该数除以10000 的余数就行了。

样例输入

6 8 1 5 3
0 2
2 1
1 0
0 5
5 1
1 4
4 3
3 5
1
3 0 5 1

样例输出

2

提示


【样例说明】



































时刻




0




1




2




3




鳄鱼位置




0




5




1




0




路线一




1




2




0




5




路线二




1




4




3




5


来源

 

[提交][状态]