题目背景

小明学习了一些魔法。

题目描述

小明有一个棋盘，棋盘有 $n$ 行，每行 $n$ 个格子，一共 $n^2$ 个格子。每个格子有一个颜色，颜色一共 $k$ 种，按 $1\sim k$ 编号。

小明还会 $m$ 种魔法，第 $i$ 种魔法有 $u_i,v_i$ 两个参数，表示小明可以选取一个颜色为 $u_i$ 的格子，并把它的颜色变为 $v_i$。

小明可以发动任意种类的魔法任意次，他想让棋盘的左上角和右下角之间存在一条由单一颜色组成的路径。但发动魔法需要消耗精力，因此他希望你帮忙求出他最少需要发动次魔法才能达到目标，或判断无解。

只能向右向下进行行走。

输入格式

第一行三个正整数 $n,m,k$，分别表示棋盘大小，魔法种类数，颜色种类数。

接下来 $n$ 行从上到下地描述了棋盘的行，每行有 $n$ 个正整数，从左到右地描述了棋盘这一行 $n$ 个格子的颜色。

接下来 $m$ 行，每行两个整数 $u,v$，表示小明会一种把格子从 $u$ 颜色变成 $v$ 颜色的魔法。

输出格式

一行一个整数，表示最少的发动魔法次数。如果无法达到目标，输出 $-1$。

2 2 2
1 2
2 1
1 2
2 1

1

样例1解释

把格子 $(1,2)$ 或者格子 $(2,1)$ 从颜色 $2$ 改成颜色 $1$ 即可，共使用 $1$ 次魔法。

3 2 3
1 3 3
2 1 3
3 3 2
2 3
1 2

3

样例2解释

先使用一次魔法将格子 $(3,3)$ 从颜色 $2$ 改成颜色 $3$，再使用两次魔法将格子 $(1,1)$ 从颜色 $1$ 改成颜色 $2$，从颜色 $2$ 改为颜色 $3$。此时路径 $(1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow (2,3)\rightarrow (3,3)$ 均为颜色 $3$，共使用 $3$ 次魔法。

数据范围

对于 $100\%$ 的数据，保证 $1\le n\le 500,1\le m\le 1000,1\le k\le 300$。保证每一种魔法都满足 $u\neq v$，保证不存在两种一模一样的魔法。

大样例

大样例下载