暂无测试数据。

蒜头君是一个和平爱好者，最近他要执行一个非常艰巨的护从任务。执行任务的过程中蒜头君需要经过一个战乱的国家。

在这个战乱的国家中总共有 $n$ 个城市，假设蒜头君需要从 $1$ 号城市进入这个国家，要从 $n$ 号城市离开这个国家。

由于受到战乱影响，国家会对城市之间道路进行管控。想要从城市 $u$ 到达城市 $v$，需要向 $u$ 城市的负责人提供一些通行材料。只有通行材料充足（蒜头君需要拥有 $u$ 城市所需的所有通行材料）才能通过 $u$ 城市到 $v$ 城市的道路到达 $v$ 城市。

这个国家共有 $k$ 种通行材料，编号为 $1,2,\cdots, k$。现在已知每个城市可以给蒜头君提供哪几种通行材料，蒜头君可以很轻松的拿到这些通行材料，并且每种通行材料是可以重复使用的。

现在蒜头君想要经过尽可能少的城市到达城市 $n$，请你帮蒜头君计算一下从城市 $1$ 到达城市 $n$ 最少需要经过多少条城市之间的道路。

另外，如果蒜头君不能从 $1$ 号城市到达 $n$ 号城市，请输出 "No Solution"。

输入格式

第一行三个整数 $n,m,k$，分别表示这个国家的城市数量、城市与城市之间的道路数量以及通行材料的种类数。

接下来 $n$ 行，每行 $k$ 个 $0$ 或 $1$，若第 $i$ 个数为 $1$，则表示该城市可以给蒜头君提供第 $i$ 种通行材料，若第 $i$ 个数为 $0$，则表示该城市不能给蒜头君提供第 $i$ 种通行材料。

接下来 $m$ 行，每行先读入两个整数 $u,v$，表示存在一条从城市 $u$ 到达城市 $v$ 的道路，再读入 $k$ 个 $0$ 或 $1$，若第 $i$ 个数为 $1$，表示需要向 $u$ 城市提供第 $i$ 种通行材料；若第 $i$ 个数为 $0$，表示不需要向 $u$ 城市提供第 $i$ 种通行材料。

输出格式

输出共一行，如果蒜头君可以从 $1$ 号城市到达 $n$ 号城市，则输出蒜头君最少需要经过多少条城市之间的道路。

如果不能从 $1$ 号城市到达 $n$ 号城市，则输出 "No Solution"。

数据范围

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

2

20 40 0
10 18
18 14
19 13
4 14
13 10
5 18
14 1
13 13
10 16
19 11
11 15
10 18
5 8
12 19
7 8
18 6
14 5
9 5
2 17
13 14
18 15
8 18
7 1
13 5
4 6
17 4
1 4
10 10
13 8
19 2
4 9
3 3
5 10
17 5
12 8
19 11
3 16
17 10
18 16
13 13

No Solution