問題一覧 > 通常問題

No.1813 Magical Stones

レベル : / AI推定難易度 : 1675 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 47
作問者 : MasKoaTS / テスター : ygussany nebocco
お気に入りにしたユーザー ProblemId : 7023 / 自分の提出
問題文最終更新日: 2024-11-28 18:48:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 327 (順位表) の他の問題:

Problem Statement

The wizard Koa is studying $N$ magic stones numbered $1,2,\dots,N$.

Magic stone $i$ $(1 \leq i \leq N)$ has magic power of magnitude $m_{i}$, and the following $M$ conditions (hereafter called the "premises") are all satisfied.

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

Here, if $M=0$, no premises are given.

From now on, Koa performs the following operation (hereafter called an "appraisal") any number of times, $0$ or more.

  • Choose $1$ pair $(x,y)$ of distinct integers satisfying $1 \leq x,y \leq N$, and use appraisal magic.
    If $m_{x} \geq m_{y}$, the information "$m_{x} \geq m_{y}$ " is obtained; otherwise, the information "$m_{x} < m_{y}$ " is obtained.

Koa performed $n$ appraisals, and by checking the $n$ pieces of information obtained against the premises above,
it was proven that $m_{1} = m_{2} = \dots = m_{N}$ holds with certainty.

Find the minimum possible value of $n$.

Constraints

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

  • $\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)$

  • All input values are integers.

Input

The input is given in the following format.

$N$ $M$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
   $\vdots$
$A_{M}$ $B_{M}$
  • Line $1$ contains $N$ and $M$ in this order, separated by a half-width space.

  • Line $(1+j)$ $(1 \leq j \leq M)$ contains $A_{j}$ and $B_{j}$ in this order, separated by a half-width space.

Output

Output the answer on $1$ line, followed by a newline.

Sample

Sample 1
Input
3 2
1 2
2 3
Output
1

Looking only at the premises, assuming $m_{1} > m_{2} > m_{3}$ leads to no contradiction.

However, if an appraisal is then performed with $(x,y)=(3,1)$, the information "$m_{3} \geq m_{1}$ " is obtained,
and it can be proven that $m_{1} = m_{2} = m_{3}$ holds with certainty.

Therefore, the answer is $1$.

Sample 2
Input
4 0
Output
4

For example, suppose Koa does the following:

  • Perform appraisal number $1$ with $(x,y)=(1,2)$

  • Perform appraisal number $2$ with $(x,y)=(2,3)$

  • Perform appraisal number $3$ with $(x,y)=(3,4)$

  • Perform appraisal number $4$ with $(x,y)=(4,1)$

Then it can be proven that $m_{1} = m_{2} = m_{3} = m_{4}$ holds with certainty.

With fewer than $4$ appraisals, it cannot be proven that $m_{1} = m_{2} = m_{3} = m_{4}$.

Sample 3
Input
4 6
1 2
2 1
1 3
3 4
4 3
4 2
Output
0

Unless $m_{1} = m_{2} = m_{3} = m_{4}$, the premises would be contradicted, so no appraisal is necessary.

Sample 4
Input
100000 2
1 2
2 1
Output
99999

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