#P18776. [Kaist2021]Dynamic Short Path

[Kaist2021]Dynamic Short Path

Dynamic Short Path

题目描述

给定一个有 nn 个顶点、n(n−1)n(n-1) 条边的有向图。对于任意不同的顶点 i,ji,j,均有一条从 ii 到 jj 的有向边,权值 w(i,j)w(i,j) 为 00、11 或 22。

按顺序处理 qq 次操作:

  • 1 a b:设从 aa 到 bb 的最短路长度为 dist⁡(a,b)\operatorname{dist}(a,b),输出 min⁡(dist⁡(a,b),2)\min(\operatorname{dist}(a,b),2)。允许 a=ba=b,此时最短路长度为 00。
  • 2 a b c:将边 a→ba\to b 的权值改为 cc,其中 a≠ba\ne b。

第二类操作至多出现 20002000 次。

输入格式

第一行两个整数 n,qn,q。

接下来 nn 行,每行 nn 个整数,第 ii 行第 jj 个整数为 w(i,j)w(i,j)。图中没有自环,但输入中的 w(i,i)w(i,i) 固定写为 00。

接下来 qq 行,每行按上述格式描述一次操作。

输出格式

对于每次第一类操作,输出一行一个整数,表示该次询问的答案。

数据范围

  • 2≤n≤6002\le n\le600,1≤q≤1061\le q\le10^6。
  • 0≤w(i,j),c≤20\le w(i,j),c\le2,1≤a,b≤n1\le a,b\le n。
  • 修改操作中 a≠ba\ne b,修改总数不超过 20002000。
  • 至少包含一次询问。

样例 1

输入

5 10
0 1 2 2 2
2 0 2 2 2
2 2 0 1 2
2 2 2 0 2
2 2 2 2 0
1 1 2
1 2 1
1 1 3
1 1 4
1 4 5
1 5 5
2 4 5 0
1 4 5
1 2 5
1 1 5

输出

1
2
2
2
2
0
0
2
2