#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y;
struct Edge
{
int next;
int dis;
int to;
}edge[100000];
struct node
{
int w,key;//w表示房间号 key表示当前房间钥匙情况
};
int head[10000];
int room[5010];//room记录每个房间钥匙情况
int vis[5010][1024];//vis记录每个房间能否行走情况
int w[6010];
int cnt=0;//编号
inline void add(int from,int to,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
inline void add_SPFA(int from,int to,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
int main()
{
cin>>n>>m>>k;
if(k==0)
{//Dijkstra
bool check[10000]={0};
long long diss[10000];
for(int i=1;i<=n;i++) diss[i]=2147483647;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
add(x,y,1);
}
int curr=1;
diss[1]=0;
long long minn;
while(!check[curr])
{
check[curr]=true;
for(int i=head[curr];i!=0;i=edge[i].next)
{
if(!check[edge[i].to]&&diss[edge[i].to]>diss[curr]+edge[i].dis)
diss[edge[i].to]=diss[curr]+edge[i].dis;
}
minn=2147483647;
for(int i=1;i<=n;i++)
{
if(!check[i]&&minn>diss[i])
{
minn=diss[i];
curr=i;
}
}
}
if(diss[n]==2147483647) cout<<"No Solution"<<endl;
else cout<<diss[n]<<endl;
}
if(k!=0)
{//SPFA
queue<node> q;//开q队列 //要写在主函数内
long long diss[10000];
for(int i=1;i<=n;i++)
{//记录房间钥匙
int key=0;
for(int j=0;j<k;j++)//j从0开始 因为这里用到位运算
{
int t;
cin>>t;
key|=(t<<j);//将t左移j位与key进行 或运算 并将运算结果赋值给key
} //或运算 有1 结果就为1 （两者都为0结果才为0）
room[i]=key;//记录i房间需要的钥匙情况
}
for(int i=1;i<=m;i++)
{//记录边的钥匙
int key=0;
cin>>x>>y;
for(int j=0;j<k;j++)
{
int t;
cin>>t;
key|=(t<<j);
}
add_SPFA(x,y,key);//在这里可以把每一条边上的钥匙情况当做该边的权值进行计算
}
for(int i=1;i<=n;i++) diss[i]=2147483647;//初始化每个点的距离为INF
diss[1]=0;
node temp;
temp.w=1;
temp.key=room[1];
vis[1][room[1]]=1;//第一个房间可走
q.push(temp);//将第一个房间入队
while(!q.empty())//SPFA算法中的2步骤 循环计算直到队列为空
{
node u=q.front();//返回队列第一个值
q.pop();//删除队列第一个值
int a=u.w,b=u.key;//记录队列第一个的房间号和钥匙情况 在这里实际上就是取出一个有父无子的房间
vis[a][b]=0;
for(int i=head[a];i;i=edge[i].next)
{
if((edge[i].dis&b)==edge[i].dis)//如果这个有父无子的房间有下一条路要求的钥匙
{
int v=edge[i].to;//v 下一个将连的房间
if(diss[v]>diss[a]+1)
{
diss[v]=diss[a]+1;
int near_key=(b|room[v]);//记录下一个将连的房间目前钥匙情况
if(!vis[v][near_key])// 如果下一个将连接的房间还未走过
{
vis[v][near_key]=1;
node t;
t.w=v;
t.key=near_key;
q.push(t);//将已确立的下一个房间入队
}
}
}
}
}
if(diss[n]==2147483647) cout<<"No Solution"<<endl;
else cout<<diss[n]<<endl;
}
return 0;
}
//来自某届石光中学信竞苟蒻学长 愿看到此文的你 努力码题 为校争光