{"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}$。注意修改是永久的。\n- 查询从 $1$ 到 $N$ 的最短用时。你出发时地铁在 $1$。\n\n## Input\n\n第一行：$N,W,D$。\n\n接下来 $W$ 行：$A_i,B_i$ 表示单向人行道。\n\n接下来一行 $N$ 个数：$S$。\n\n接下来 $D$ 行：$X_i,Y_i$，保证 $2\\leq X_i,Y_i\\leq N,X_i\\neq Y_i$。\n\n## Output\n\n$D$ 行，每天的答案。\n\n[samples]\n\n## Note\n\n$$3\\leq N\\leq 200000,0\\leq W\\leq 200000,1\\leq D\\leq 200000$$\n\n译自 [CCC2021 S4](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。\n\n请注意常数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9026","tags":["图论","2021","CCC（加拿大）","最短路"],"sample_group":[["4 3 3\n1 2\n3 4\n4 1\n1 4 3 2\n3 4\n4 2\n3 2\n","1\n2\n3\n"]],"created_at":"2026-03-03 11:09:25"}}