問題一覧 > 通常問題

No.1660 Matrix Exponentiation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : 👑 箱箱 / テスター : stoqstoq 👑 ygussanyygussany
11 ProblemId : 6778 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 00:09:57

問題文

$N$ 行 $N$ 列の行列 $A$ があります。$i=1,2,\ldots,K$ に対し $A$ の $r_i$ 行 $c_i$ 列成分は $1$ で、それ以外の成分は $0$ です。

$A^m$ が零行列となるような正の整数 $m$ が存在するかを判定し、存在するときは $m$ の最小値を求めてください。

制約

  • $1\le N\le 10^5$
  • $0\le K\le \min(N^2,10^5)$
  • $1\le r_i,c_i\le N$
  • $i\ne j$ ならば $(r_i,c_i)\ne (r_j,c_j)$
  • 入力はすべて整数

入力

$N$ $K$
$r_1$ $c_1$
$r_2$ $c_2$
$\vdots$
$r_K$ $c_K$

出力

$A^m$ が零行列となるような正の整数 $m$ が存在するときは、$m$ の最小値を出力してください。存在しないときは $-1$ を出力してください。

サンプル

サンプル1
入力
3 3
1 2
1 3
2 3
出力
3

$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}$ なので、答えは $3$ です。

サンプル2
入力
3 3
1 1
2 2
3 3
出力
-1

任意の $m$ に対し、$A^m$ は零行列になりません。

サンプル3
入力
1 0
出力
1

$A$ は零行列です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。