该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

“欺师灭祖，老东西们自然不肯放过我，来罢！”

“三味神风，久未用也！”

“黄沙，旋吧！”

神风怒扬，黄沙遮天。

你不禁后退几步，沙尘几乎将你埋没。无意间，怀中定风珠熠熠生辉，三丈之内，风沙止。你终于能看清黄毛貂鼠手中起落的是什么物事。

闭目佛头，其中必有蹊跷。

夺了它！

题目描述

黄风阵好似一张由 \(n\) 个节点和 \(m\) 条边构成的一张图，你现在位于 \(1\) 号结点，黄风大圣正在 \(n\) 号结点，你需要 以一个时间单位通过一条边的速度 尽快疾奔至 \(n\) 号结点，夺下佛头。

但是这并非易事，黄风大圣非等闲之辈，它会以 \(k\) 个时间单位为周期，每一个时间单位都会挥出一道风沙刃，将一些 边 封锁，该时间单位内你不能通过被封锁的 边 ，封锁一个时间单位内一些边的风沙刃 会在下一个时间单位消散 。在 每一个周期的同一个时间单位 内，风沙刃封锁的边都是一样的。

你可以 在原地停止几个时间单位 来等待风沙刃消散。

那么，你需要多久才能夺下佛头呢？

或者，不可能拿下佛头了，那便断送了这天命吧。

输入格式

第一行两个整数 \(n、m\) ,表示地图大小。

接下来 \(m\) 行，每行两个整数表示两点之间存在一条边。

再接下来一行一个整数 \(k\) 表示周期时长。

然后的每一行两个整数，表示这两点之间的边在该时间单位不可通行，0 0 表示对周期中的一个时间单位不可通行边描述完毕，保证恰好有 \(k\) 个 0 0。

输出格式

一行一个整数，表示从 \(1\) 号结点到达 \(n\) 号结点的最短时间，如果到达不了，输出 No solution.。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

3

提示

风沙刃也可以不封锁任何边，如样例 #1 的第三个时间单位。

不保证不存在重边、自环。

对于 \(20\%\) 的数据，保证 \(1 \leqslant n\leqslant 10\)。

对于 \(100\%\) 的数据，保证 \(1 \leqslant n\leqslant 1\times 10^{2},1 \leqslant m\leqslant 5\times 10^{2},0 \leqslant k\leqslant 10\)。

对于样例#3，满足对 \(20\%\) 数据的约束条件。

对于样例#4，满足对 \(100\%\) 数据的约束条件。

---

“在下斗胆求高人出手，助我大王降妖。”

“黄风大王宅心仁厚，是灵山来的正道弟子，你放心去，结个善缘。”