[CCC 2021 S4] Daily Commute

Luogu

IDLGP9026

Time1500ms

Memory128MB

DifficultyP4

图论2021CCC（加拿大）最短路

已知有 $N$ 个地铁站，你家在 $1$，学校在 $N$。有 $W$ 条单向人行道。经过需要一分钟。此外还有一条环形地铁线路，依次经过 $S_1,S_2,\cdots,S_N$，且保证 $S_1=1$。每天**有且仅有**一辆地铁在 $0$ 时刻从 $S_1$ 出发，并且恰好在第 $i$ 分钟到达 $S_i$。在接下来 $D$ 天中： - 交换 $S_{X_i}$ 和 $S_{Y_i}$。注意修改是永久的。 - 查询从 $1$ 到 $N$ 的最短用时。你出发时地铁在 $1$。 ## Input 第一行：$N,W,D$。接下来 $W$ 行：$A_i,B_i$ 表示单向人行道。接下来一行 $N$ 个数：$S$。接下来 $D$ 行：$X_i,Y_i$，保证 $2\leq X_i,Y_i\leq N,X_i\neq Y_i$。 ## Output $D$ 行，每天的答案。 [samples] ## Note $$3\leq N\leq 200000,0\leq W\leq 200000,1\leq D\leq 200000$$ 译自 [CCC2021 S4](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。请注意常数。

Samples

Input #1

Output #1

1
2
3

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2021 S4] Daily Commute",
    "description": {
      "content": "已知有 $N$ 个地铁站，你家在 $1$，学校在 $N$。 有 $W$ 条单向人行道。经过需要一分钟。 此外还有一条环形地铁线路，依次经过 $S_1,S_2,\\cdots,S_N$，且保证 $S_1=1$。每天**有且仅有**一辆地铁在 $0$ 时刻从 $S_1$ 出发，并且恰好在第 $i$ 分钟到达 $S_i$。 在接下来 $D$ 天中： - 交换 $S_{X_i}$ 和 $S_{Y_i",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9026"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "已知有 $N$ 个地铁站，你家在 $1$，学校在 $N$。\n\n有 $W$ 条单向人行道。经过需要一分钟。\n\n此外还有一条环形地铁线路，依次经过 $S_1,S_2,\\cdots,S_N$，且保证 $S_1=1$。每天**有且仅有**一辆地铁在 $0$ 时刻从 $S_1$ 出发，并且恰好在第 $i$ 分钟到达 $S_i$。\n\n在接下来 $D$ 天中：\n\n- 交换 $S_{X_i}$ 和 $S_{Y_i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments