说明

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

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

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

输入格式

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

第2 到M + 1 行，给出石桥的相关信息。每行两个整数x 和y，0 ≤ x, y ≤ N–1，表示这座石桥连接着编号为x 和y 的两座石墩。

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

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

输出格式

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

提示

【样例说明】

来源