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 CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 58;

struct StronglyConnectedComponents
{
  vector< vector< int > > gg, rg;
  vector< pair< int, int > > edges;
  vector< int > comp, order, used;

  StronglyConnectedComponents(size_t v) : gg(v), rg(v), comp(v, -1), used(v, 0) {}

  void add_edge(int x, int y)
  {
    gg[x].push_back(y);
    rg[y].push_back(x);
    edges.emplace_back(x, y);
  }

  int operator[](int k)
  {
    return (comp[k]);
  }

  void dfs(int idx)
  {
    if(used[idx]) return;
    used[idx] = true;
    for(int to : gg[idx]) dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt)
  {
    if(comp[idx] != -1) return;
    comp[idx] = cnt;
    for(int to : rg[idx]) rdfs(to, cnt);
  }

  void build(vector< vector< int > > &t)
  {
    for(int i = 0; i < gg.size(); i++) dfs(i);
    reverse(begin(order), end(order));
    int ptr = 0;
    for(int i : order) rdfs(i, ptr), ptr++;

    t.resize(ptr);
    set< pair< int, int > > connect;
    for(auto &e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      if(connect.count({x, y})) continue;
      t[x].push_back(y);
      connect.emplace(x, y);
    }
  }
};

int H, W, N;
int link[500][500];
bool mine[500][500];
int linked[250000];
int64 lazy[250000];

int main()
{
  cin >> H >> W >> N;

  StronglyConnectedComponents scc(H * W);

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      int y, x;
      cin >> y >> x;
      link[i][j] = y * W + x;
      linked[i * W + j] = link[i][j];
      if(y == i && x == j) {
        mine[i][j] = true;
      } else {
        scc.add_edge(i * W + j, link[i][j]);
      }
    }
  }

  vector< vector< int > > g;
  scc.build(g);
  vector< vector< int > > ventex(g.size());
  vector< set< int > > query(g.size());
  vector< int > beet(g.size(), 0);
  vector< int > dinamic(H * W, -1);

  for(int i = 0; i < H * W; i++) {
    ventex[scc[i]].push_back(i);
  }
  for(int i = 0; i < g.size(); i++) {
    if(ventex[i].empty()) continue;
    if(ventex[i].size() == 1 && !mine[ventex[i][0] / W][ventex[i][0] % W]) continue;
    beet[i] = true;
  }

  for(int i = 0; i < g.size(); i++) {
    if(ventex[i].empty()) continue;
    if(beet[i]) {
      int now = ventex[i][0];
      int ptr = 0;
      while(dinamic[now] == -1) {
        dinamic[now] = ptr++;
        now = linked[now];
      }
    }
  }

  vector< priority_queue< pair< int, int >, vector< pair< int, int > >, greater< pair< int, int > > > > que(g.size());

  for(int i = 0; i < N; i++) {
    int y, x;
    cin >> y >> x;
    y = y * W + x;

    if(beet[scc[y]]) {
      que[scc[y]].emplace(0, dinamic[y]);
    } else {
      query[scc[y]].emplace(beet[scc[y]] ? dinamic[y] : 0);
    }
  }


  int64 res = INF;
  for(int i = 0; i < g.size(); i++) {

    if(ventex[i].empty()) continue;
    if(!beet[i]) {
      int future = linked[ventex[i][0]];
      bool commit = beet[scc[future]];

      if(commit || query[i].size() < query[scc[future]].size()) {
        for(int j : query[i]) {
          int64 nxt = j + 1 + lazy[i] - lazy[scc[future]];
          if(commit) {
            que[scc[future]].emplace(nxt, dinamic[future] + lazy[scc[future]]);
            continue;
          }
          if(query[scc[future]].count(nxt)) {
            res = min(res, nxt + lazy[scc[future]]);
          } else {
            query[scc[future]].insert(nxt);
          }
        }
      } else {
        lazy[i]++;
        for(int j : query[scc[future]]) {
          int64 nxt = j - lazy[i] + lazy[scc[future]];
          if(query[i].count(nxt)) {
            res = min(res, nxt + lazy[i]);
          } else {
            query[i].insert(nxt);
          }
        }
        swap(lazy[i], lazy[scc[future]]);
        swap(query[i], query[scc[future]]);
      }
    }
  }

  for(int i = 0; i < g.size(); i++) {
    if(ventex[i].empty()) continue;
    if(beet[i]) {
      vector< int > ss(ventex[i].size(), 0);
      while(!que[i].empty()) {
        auto s = que[i].top();
        que[i].pop();
        int nxt = (s.first - s.second + ventex[i].size()) % ventex[i].size();
        if(query[i].count(nxt)) {
          res = min(res, (int64) s.first);
        } else {
          query[i].insert(nxt);
        }

      }
    }
  }


  if(res == INF) {
    cout << -1 << endl;
  } else {
    cout << res << endl;
  }
}