問題一覧 > 通常問題

No.1813 Magical Stones

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 36
作問者 : MasKoaTSMasKoaTS / テスター : nebocconebocco 👑 ygussanyygussany
3 ProblemId : 7023 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-29 22:01:22

問題文

魔法使いのコアさんは、$1,2,\dots,N$ の番号が付いた $N$ 個の魔石を研究しています。

魔石 $i$ $(1 \leq i \leq N)$ は大きさ $m_{i}$ の魔力を持っており、次の $M$ 個の条件(以下「前提」と呼ぶ)を満たします。

  • $m_{A_{j} } \geq m_{B_{j} }$ $(1 \leq j \leq M)$

ただし、$M=0$ の場合、前提は何も与えられません。

また、コアさんは次の操作(以下「鑑定」と呼ぶ)を $0$ 回以上好きな回数だけ行います。

  • $1 \leq x,y \leq N$ を満たす異なる整数の組 $(x,y)$ を $1$ つ選び、鑑定魔法を使う。
    $m_{x} \geq m_{y}$ ならば「$m_{x} \geq m_{y}$ 」という情報、そうでなければ「$m_{x} < m_{y}$ 」という情報が得られる。

コアさんが鑑定を $n$ 回行い、そこで得た $n$ 個の情報と先の前提を照らし合わせたところ、
$m_{1} = m_{2} = \dots = m_{N}$ が 確実に 成り立つことが証明されました。

このとき、$n$ の値としてあり得るものの最小値を求めてください。

制約

  • $2 \leq N \leq 10^{5}$

  • $m_{i}$ $(1 \leq i \leq N)$ は実数

  • $\displaystyle 0 \leq M \leq \min ( 2 \times 10^{5}, N \times (N-1) )$

  • $1 \leq A_{j},B_{j} \leq N$ $(1 \leq j \leq M)$

  • $A_{j} \neq B_{j}$ $(1 \leq j \leq M)$

  • $(A_{i},B_{i}) \neq (A_{j},B_{j})$ $(1 \leq i < j \leq M)$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
   $\vdots$
$A_{M}$ $B_{M}$
  • $1$ 行目には $N$ と $M$ がこの順に空白区切りで与えられる

  • $(1+j)$ $(1 \leq j \leq M)$ 行目には $A_{j}$ と $B_{j}$ がこの順に空白区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

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

前提のみを見た場合、$m_{1} > m_{2} > m_{3}$ であると考えても矛盾しません。

しかし、この後に $(x,y)=(3,1)$ として鑑定を行った場合、「$m_{3} \geq m_{1}$ 」という情報が得られ、
$m_{1} = m_{2} = m_{3}$ が確実に成り立つことが証明できます。

よって、答えは $1$ となります。

サンプル2
入力
4 0
出力
4

例えば、

  • $(x,y)=(1,2)$ として $1$ 回目の鑑定を行う

  • $(x,y)=(2,3)$ として $2$ 回目の鑑定を行う

  • $(x,y)=(3,4)$ として $3$ 回目の鑑定を行う

  • $(x,y)=(4,1)$ として $4$ 回目の鑑定を行う

とすれば、$m_{1} = m_{2} = m_{3} = m_{4}$ が確実に成り立つことが証明できます。

鑑定回数が $4$ 回未満の場合、$m_{1} = m_{2} = m_{3} = m_{4}$ であることは証明できません。

サンプル3
入力
4 6
1 2
2 1
1 3
3 4
4 3
4 2
出力
0

$m_{1} = m_{2} = m_{3} = m_{4}$ でなければ前提に矛盾するので、鑑定を行う必要はありません。

サンプル4
入力
100000 2
1 2
2 1
出力
99999

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