Problem: problem

A dance party with $ N $ people is held at a dance hall. The dance hall is divided into $ H $ vertical and $ W $ horizontal grids, with $ (0,0) $ in the upper left, $ r $ squares from the top, and $ c $ squares from the left. The coordinates of the grid of the eyes are expressed as $ (r, c) $. The initial position of the $ i $ th participant is $ (R_i, C_i) $, and the $ (i, j) $ grid contains $ (r_ {ij}, c_ {ij}) $. ..

Each participant simultaneously moves to the endless music as follows.

* When the coordinates at that time are $ (i, j) $, jump to $ (r_ {ij}, c_ {ij}) $.



Each grid is narrow and will collide if two or more participants move to the same grid at the same time. However, it is assumed that there is no collision in the air. When you heard this, you were worried that two or more participants would collide after the jump. Therefore, I decided to find out if there was a possibility of a collision, and if so, how many jumps the collision would occur after.



output

If a collision occurs, output in one line how many jumps it will occur after. If not, output -1. Also, output a line break at the end.

Example

Input

2 2 2
1 0 0 1
0 0 1 0
0 0
0 1


Output

-1

Solution (in JAVA):

Solution:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.InputMismatchException;

public class Main {
	InputStream is;

	int __t__ = 1;
	int __f__ = 0;
	int __FILE_DEBUG_FLAG__ = __f__;
	String __DEBUG_FILE_NAME__ = "src/H1";

	FastScanner in;
	PrintWriter out;
	
	int H, W;
	int toID(int r, int c) {
		return r * W + c;
	}
	
	int MAX = 20;
	public void solve() {
		this.H = in.nextInt();
		this.W = in.nextInt();
		int N = in.nextInt();
		
		int M = H * W;
		int[][] g = new int[M][MAX];
		
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				int r = in.nextInt(), c = in.nextInt();
				int from = toID(i, j);
				int to = toID(r, c);
				g[from][0] = to;
			}
		}
		
		for (int i = 1; i < MAX; i++) {
			for (int from = 0; from < M; from++) {
				int to = g[from][i-1];
				g[from][i] = g[to][i-1];
			}
		}
		
		int[] ps = new int[N];
		for (int i = 0; i < N; i++) {
			int r = in.nextInt(), c = in.nextInt();
			ps[i] = toID(r, c);
		}
		
		int lo = 0, hi = M + 10;
		while (hi - lo > 1) {
			int mid = (lo + hi) / 2;
			if (collide(g, ps, mid))
				hi = mid;
			else
				lo = mid;
		}
		System.out.println(hi == M + 10 ? -1 : hi);
	}
	
	HashSet<Integer> hash = new HashSet<>();
	boolean collide(int[][] g, int[] ps, int mid) {
		int N = ps.length;
		hash.clear();
		for (int p : ps) {
			int now = p;
			for (int b = mid, i = 0; b > 0; b >>= 1, i++) {
				if ((b & 1) == 0) continue;
				now = g[now][i];
			}
			if (hash.contains(now))
				return true;
			hash.add(now);
		}
		return false;
	}

	public void run() {
		if (__FILE_DEBUG_FLAG__ == __t__) {
			try {
				is = new FileInputStream(__DEBUG_FILE_NAME__);
			} catch (FileNotFoundException e) {
				// TODO ????????????????????? catch ????????????
				e.printStackTrace();
			}
			System.out.println("FILE_INPUT!");
		} else {
			is = System.in;
		}
		in = new FastScanner(is);
		out = new PrintWriter(System.out);

		Thread t = new Thread(null, new Runnable() {
			@Override
			public void run() {
				solve();
			}
		}, "lul", 1 << 30);
		t.start();
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

		int[][] nextIntMap(int n, int m) {
			int[][] map = new int[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextIntArray(m);
			}
			return map;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

		long[][] nextLongMap(int n, int m) {
			long[][] map = new long[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextLongArray(m);
			}
			return map;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

		double[][] nextDoubleMap(int n, int m) {
			double[][] map = new double[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextDoubleArray(m);
			}
			return map;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}