No.1813 Magical Stones
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
MasKoaTS