时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H是一名出色的情报人员，这天他需要穿过敌人的封锁线从情报站回到总部。

　　地图上显示，情报站与总部的交通上总共有 \(m\) 条双向道路和 \(n\) 个交叉路口，对于每条道路，小H总是可以用 1 分钟时间走完；而在每个交叉路口，小H都能选择躲藏和行走。敌人对一些道路的巡逻是周期循环的，他们总是以分钟为单位巡逻某条道路，在该分钟过去后离开。如果在某一分钟内某条道路有人巡逻，那么小H在这一分钟内将无法穿过这条道路。

　　时间紧迫，小H必须尽快到达总部。那么他该如何行走才能用最短的时间到达总部呢？

【输入格式】

　　输入数据第一行有两个整数 \(n\) 和 \(m\)，代表有 \(n\) 个结点 \(m\) 条边。1 号结总是代表情报站，\(n\) 号结点总是代表总部。
　　接下去 \(m\) 行每行有两个小于等于 \(n\) 的正整数，分别代表一条道路连接的交叉路口编号（如果边被重复描述，仍表示只有一条边）。道路是双向的。
　　再接下去一行有一个整数 \(k\) 代表周期长度。
　　后面的数据都是对周期巡逻边的描述，每行有两个整数，表示被巡逻的边。0 0 则表示对周期中某一分钟的巡逻边描述结束。数据保证在该段恰存在 \(k\) 个 0 0。

【输出格式】

　　输出数据仅有一行，如果小H可以到达总部，则输出到达总部的最短时间。如果不能到达则输出“No solution.”

【输入输出样例1】

　Input

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

　Output

3

【样例1解释】

　　样例给出的地图如下，其中结点1为情报站，5为总部，其余为交叉路口。

　　巡逻周期为4分钟：
　　每个周期的第1分钟有巡逻的边为{(1,2),(2,4),(4,5)}
　　每个周期的第2分钟有巡逻的边为{(1,3),(2,3),(3,5)}
　　每个周期的第3分钟有巡逻的边为{(3,4),(4,5)}
　　每个周期的第4分钟没有巡逻边。
　　这样，小H可以在第一分钟走边(1,3)，第二分钟躲藏，第3分钟走边(3,5)，消耗3分钟，时间最短。

【输入输出样例2】

　Input

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

　Output

10

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤100\)，\(1≤m≤500\)，\(0≤k≤10\)。

【来源】

　　Mr.he