1121: 小X的密室

小 X 正困在一个密室里，他希望尽快逃出密室。

密室中有N个房间，初始时，小 X 在1号房间，而出口在N号房间。

密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间X到房间Y的通道。另外，想要通过某个传送门，就必须具备一些种类的钥匙（每种钥匙都要有才能通过）。幸运的是，钥匙在打开传送门的封印后，并不会消失。

然而，通过密室的传送门需要耗费大量的时间，因此，小 X 希望通过尽可能少的传送门到达出口，你能告诉小 X 这个数值吗？

另外，小 X 有可能不能逃出这个密室，如果是这样，请输出 "No Solution"。

第一行三个整数N,M,K，分别表示房间的数量、传送门的数量以及钥匙的种类数。

接下来N行，每行K个0或1，若第i个数为1，则表示该房间内有第i种钥匙，若第i个数为0，则表示该房间内没有第i 种钥匙。

接下来M行，每行先读入两个整数X,Y，表示该传送门是建立在X号房间，通向Y号房间的，再读入K个0或1，若第i个数为1，则表示通过该传送门需要i种钥匙，若第i个数为0，则表示通过该传送门不需要第i种钥匙。

输出一行一个 "No Solution"，或一个整数，表示最少通过的传送门数。

样例输入1：
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 

样例输入3
20 50 0
8 10 
7 17 
5 11 
14 20 
20 16 
8 19 
12 11 
18 7 
17 5 
4 15 
16 11 
11 8 
10 12 
8 9 
16 8 
3 16 
1 6 
3 20 
6 10 
11 12 
6 8 
18 17 
14 17 
3 11 
4 19 
9 2 
8 6 
13 2 
5 2 
12 19 
8 10 
14 7 
6 12 
6 4 
13 2 
8 7 
13 19 
17 9 
3 14 
18 20 
2 14 
4 17 
20 15 
14 15 
2 15 
7 20 
12 12 
18 10 
15 9 
15 9 

样例输出1：
2

样例输出2：
No Solution

样例输出3
4