시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7.5 초 (추가 시간 없음) | 1024 MB | 149 | 30 | 15 | 15.957% |
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.
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