{"raw_statement":[{"iden":"statement","content":"Okabe likes to be able to walk through his city on a path lit by street lamps. That way, he doesn't get beaten up by schoolchildren.\n\nOkabe's city is represented by a 2D grid of cells. Rows are numbered from 1 to _n_ from top to bottom, and columns are numbered 1 to _m_ from left to right. Exactly _k_ cells in the city are lit by a street lamp. It's guaranteed that the top-left cell is lit.\n\nOkabe starts his walk from the top-left cell, and wants to reach the bottom-right cell. Of course, Okabe will only walk on lit cells, and he can only move to adjacent cells in the up, down, left, and right directions. However, Okabe can also temporarily light all the cells in any single row or column at a time if he pays 1 coin, allowing him to walk through some cells not lit initially.\n\nNote that Okabe can only light a single row or column at a time, and has to pay a coin every time he lights a new row or column. To change the row or column that is temporarily lit, he must stand at a cell that is lit initially. Also, once he removes his temporary light from a row or column, all cells in that row/column not initially lit are now not lit.\n\nHelp Okabe find the minimum number of coins he needs to pay to complete his walk!"},{"iden":"input","content":"The first line of input contains three space-separated integers _n_, _m_, and _k_ (2 ≤ _n_, _m_, _k_ ≤ 104).\n\nEach of the next _k_ lines contains two space-separated integers _r__i_ and _c__i_ (1 ≤ _r__i_ ≤ _n_, 1 ≤ _c__i_ ≤ _m_) — the row and the column of the _i_\\-th lit cell.\n\nIt is guaranteed that all _k_ lit cells are distinct. It is guaranteed that the top-left cell is lit."},{"iden":"output","content":"Print the minimum number of coins Okabe needs to pay to complete his walk, or _\\-1_ if it's not possible."},{"iden":"examples","content":"Input\n\n4 4 5\n1 1\n2 1\n2 3\n3 3\n4 3\n\nOutput\n\n2\n\nInput\n\n5 5 4\n1 1\n2 1\n3 1\n3 2\n\nOutput\n\n\\-1\n\nInput\n\n2 2 4\n1 1\n1 2\n2 1\n2 2\n\nOutput\n\n0\n\nInput\n\n5 5 4\n1 1\n2 2\n3 3\n4 4\n\nOutput\n\n3"},{"iden":"note","content":"In the first sample test, Okabe can take the path , paying only when moving to (2, 3) and (4, 4).\n\nIn the fourth sample, Okabe can take the path , paying when moving to (1, 2), (3, 4), and (5, 4)."}],"translated_statement":[{"iden":"statement","content":"Okabe 喜欢在被路灯照亮的路径上穿行于他的城市，这样他就不会被学生打。\n\nOkabe 的城市由一个二维网格表示，行从上到下编号为 #cf_span[1] 到 #cf_span[n]，列从左到右编号为 #cf_span[1] 到 #cf_span[m]。城市中恰好有 #cf_span[k] 个单元格被路灯照亮。保证左上角的单元格是被照亮的。\n\nOkabe 从左上角单元格出发，希望到达右下角单元格。当然，Okabe 只会在被照亮的单元格上行走，并且他只能向上下左右四个方向移动到相邻的单元格。然而，Okabe 也可以通过支付 #cf_span[1] 枚硬币，临时照亮任意一行或一列中的所有单元格，从而能够穿过一些最初未被照亮的单元格。\n\n注意，Okabe 每次只能临时照亮一行或一列，并且每次点亮新的行或列都必须支付一枚硬币。要更改当前临时照亮的行或列，他必须站在一个最初被照亮的单元格上。此外，一旦他取消对某行或某列的临时照明，该行或列中所有最初未被照亮的单元格将再次变为未照亮状态。\n\n请帮助 Okabe 找出他完成步行所需的最少硬币数！\n\n输入的第一行包含三个空格分隔的整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[2 ≤ n, m, k ≤ 104]）。\n\n接下来的 #cf_span[k] 行每行包含两个空格分隔的整数 #cf_span[ri] 和 #cf_span[ci]（#cf_span[1 ≤ ri ≤ n]，#cf_span[1 ≤ ci ≤ m]）——第 #cf_span[i] 个被照亮单元格的行和列。\n\n保证所有 #cf_span[k] 个被照亮的单元格互不相同，且左上角单元格是被照亮的。\n\n请输出 Okabe 完成步行所需的最少硬币数，如果不可能完成则输出 _-1_。\n\n在第一个样例中，Okabe 可以沿着路径行走，仅在移动到 #cf_span[(2, 3)] 和 #cf_span[(4, 4)] 时支付硬币。\n\n在第四个样例中，Okabe 可以沿着路径行走，在移动到 #cf_span[(1, 2)]、#cf_span[(3, 4)] 和 #cf_span[(5, 4)] 时支付硬币。"},{"iden":"input","content":"输入的第一行包含三个空格分隔的整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[2 ≤ n, m, k ≤ 104]）。接下来的 #cf_span[k] 行每行包含两个空格分隔的整数 #cf_span[ri] 和 #cf_span[ci]（#cf_span[1 ≤ ri ≤ n]，#cf_span[1 ≤ ci ≤ m]）——第 #cf_span[i] 个被照亮单元格的行和列。保证所有 #cf_span[k] 个被照亮的单元格互不相同，且左上角单元格是被照亮的。"},{"iden":"output","content":"请输出 Okabe 完成步行所需的最少硬币数，如果不可能完成则输出 _-1_。"},{"iden":"examples","content":"输入\n4 4 5\n1 1\n2 1\n2 3\n3 3\n4 3\n输出\n2\n\n输入\n5 5 4\n1 1\n2 1\n3 1\n3 2\n输出\n-1\n\n输入\n2 2 4\n1 1\n1 2\n2 1\n2 2\n输出\n0\n\n输入\n5 5 4\n1 1\n2 2\n3 3\n4 4\n输出\n3"},{"iden":"note","content":"在第一个样例中，Okabe 可以沿着路径行走，仅在移动到 #cf_span[(2, 3)] 和 #cf_span[(4, 4)] 时支付硬币。在第四个样例中，Okabe 可以沿着路径行走，在移动到 #cf_span[(1, 2)]、#cf_span[(3, 4)] 和 #cf_span[(5, 4)] 时支付硬币。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a graph where:  \n- $ V = \\{ (i, j) \\in \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} \\mid \\text{cell } (i,j) \\text{ is initially lit} \\} \\cup \\{ \\text{temporary row/column states} \\} $  \n- Each vertex represents a position $(i, j)$ **and** the current set of temporarily lit rows and columns.  \n- An edge exists between two vertices if Okabe can move from one to the other by:  \n  (a) Moving to an adjacent (up/down/left/right) **initially lit** cell, or  \n  (b) Paying 1 coin to temporarily light an entire row $i$ or column $j$, **only if currently standing on an initially lit cell**, and transitioning to all cells in that row/column (temporarily accessible).  \n\nLet $ L \\subseteq \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the set of $k$ initially lit cells, with $(1,1) \\in L$.  \nLet $ s = (1,1) $ be the start, $ t = (n,m) $ be the target.  \n\n**Constraints**  \n1. $ 2 \\leq n, m, k \\leq 10^4 $  \n2. $ |L| = k $, all elements of $L$ are distinct.  \n3. $(1,1) \\in L$  \n4. Temporary lighting:  \n   - Only one row or column can be lit at a time.  \n   - To activate a new row/column, Okabe must be on an **initially lit** cell.  \n   - Deactivating a temporary row/column reverts non-lit cells to unlit.  \n5. Movement: Only to adjacent (4-directional) cells that are either initially lit or currently temporarily lit.  \n\n**Objective**  \nFind the minimum number of coins (i.e., temporary row/column activations) required to reach $(n, m)$ from $(1, 1)$, or return $-1$ if impossible.  \n\n**State Representation**  \nEach state is a tuple $ (r, c, R, C) $, where:  \n- $ (r, c) \\in L $: current position on an initially lit cell.  \n- $ R \\subseteq \\{1, \\dots, n\\} $: currently active temporarily lit rows (at most one).  \n- $ C \\subseteq \\{1, \\dots, m\\} $: currently active temporarily lit columns (at most one).  \n\nBut since only one row or column can be active at a time, we can represent state as:  \n- $ (r, c, t) $, where $ t \\in \\{ \\text{none}, \\text{row } i, \\text{col } j \\} $  \n\n**Reformulated Objective**  \nFind the shortest path (minimum coin cost) in the state space from $ ((1,1), \\text{none}) $ to any state $ ((n,m), \\cdot) $, where transitions are:  \n- Move to adjacent initially lit cell: cost 0.  \n- Activate a row $i$ or column $j$ (if current $(r,c) \\in L$): cost 1, and can move freely along row $i$ or column $j$ (including non-lit cells).  \n- Deactivate current temporary row/column: cost 0, but only if moving to an initially lit cell.  \n\n**Final Formal Statement**  \nMinimize the number of temporary row/column activations (coins) to reach $(n, m)$ from $(1,1)$, moving only on initially lit or currently temporarily lit cells, with at most one temporary row or column active at a time, and activation only allowed from initially lit positions. Return $-1$ if unreachable.","simple_statement":null,"has_page_source":false}