2241: 惊险道路

飞飞做了一个梦，梦里他遇到了惊险道路，道路和道路相连的地方是结点。这些道路中的某些道路在某些时刻会变得危险重重、刀光剑影，完全不可走。但是这种情况只会持续1分钟，过了这1分钟，可能就变成了坦途，可以通行了。这些道路的不可走性是周期的。假设该周期是k，道路s在第1分钟不可走，然后在第k+1分钟也是不可走的，依次类推。 

道路和道路交叉的点可以有地方隐藏，飞飞面对某条道路时，可以选择走或隐藏。飞飞有神奇的能力，每次都是花费恰好1分钟的时间走完一条道路。 

梦里有n个结点，m条道路，飞飞站在1号结点上，他要去n号结点。飞飞被这梦折磨的精疲力尽，但是醒来后发现这是个好问题，值得研究。他邀请你来试试，求出从1号点到n号点的最短时间，如果无法到达，则输出无解。

从文件"dangerpath.in"读入数据。 

第一行两个正整数n和m。 

后面接着有m行，每行两个数据a和b，代表一条道路连接的两个结点，可能会有重复的道路描述。 

接着是一个整数k，表示循环周期。

再接着是k组数据，每组数据有若干行，每行表示在该分钟该条道路不可走，每组数据最后以 0 0 结束。

输出到文件"dangerpath.out"。 

如果能到达n号结点，则输出最短时间。如果到达不了，则输出”No solution.”。注意：不带双引号。

4 5
3 4
2 3
1 3
2 4
1 2
3
1 2
0 0
1 3
3 4
2 3
0 0
2 4
0 0

3