23171번 - Dynamic Short Path 다국어

문제

You are given a weighted directed graph with $n$ vertices and $n(n-1)$ edges. For any pair of two distinct vertices 1ドル \le i, j \le n,ドル there exists an edge with integer weight $w(i, j)$ where 0ドル \le w(i, j) \le 2$.

Process the following $q$ queries:

• 1 a b: Let $dist(a, b)$ be the length of the shortest directed path from vertex $a$ to vertex $b$ (1ドル \le a, b \le n$). Output the value $\min(dist(a, b), 2)$.
• 2 a b c: Update $w(a, b)$ to $c$ (1ドル \le a, b \le n, 0 \le c \le 2, a \neq b$).

There are at most 2ドル,000円$ queries of type 2.

입력

The first line contains two integers $n$ and $q$ (2ドル \le n \le 600, 1 \le q \le 10^6$).

The next $n$ lines contain $n$ integers. The $j$-th integer of the $i$-th line is $w(i, j)$ (0ドル \le w(i, j) \le 2$). $w(i, i)$ will be denoted as 0ドル$ for all $i$ even though no such edge exists.

The next $q$ lines contain several integers denoting the queries in the described form.

There is at least 1 query of type 1.

There are at most 2ドル,000円$ queries of type 2.

출력

For each query of type 1, output a single integer denoting the answer to that query. Each answer should go on its own line.

제한

힌트