No.1660 Matrix Exponentiation
箱星
stoq
ygussanyProblem Statement
There is a matrix $A$ with $N$ rows and $N$ columns. For $i=1,2,\ldots,K$, the entry of $A$ in row $r_i$ and column $c_i$ is $1$, and all other entries are $0$.
Determine whether there exists a positive integer $m$ such that $A^m$ is the zero matrix, and if it exists, find the minimum value of $m$.
Constraints
- $1\le N\le 10^5$
- $0\le K\le \min(N^2,10^5)$
- $1\le r_i,c_i\le N$
- If $i\ne j$, then $(r_i,c_i)\ne (r_j,c_j)$
- All input values are integers
Input
$N$ $K$ $r_1$ $c_1$ $r_2$ $c_2$ $\vdots$ $r_K$ $c_K$
Output
If there exists a positive integer $m$ such that $A^m$ is the zero matrix, print the minimum value of $m$. If it does not exist, print $-1$.
Sample
Sample 1
Input
3 3 1 2 1 3 2 3
Output
3
Since $A=\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}, A^2=\begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}, A^3=\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$, the answer is $3$.
Sample 2
Input
3 3 1 1 2 2 3 3
Output
-1
For any $m$, $A^m$ is not the zero matrix.
Sample 3
Input
1 0
Output
1
$A$ is the zero matrix.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。