{"raw_statement":[{"iden":"problem statement","content":"You are given a simple directed graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ is a directed edge from vertex $u_i$ to vertex $v_i$.\nYou may perform the following operation zero or more times.\n\n*   Choose distinct vertices $x$ and $y$ such that there is no directed edge from vertex $x$ to vertex $y$, and add a directed edge from vertex $x$ to vertex $y$.\n\nFind the minimum number of times you need to perform the operation to make the graph satisfy the following condition.\n\n*   For every triple of distinct vertices $a$, $b$, and $c$, if there are directed edges from vertex $a$ to vertex $b$ and from vertex $b$ to vertex $c$, there is also a directed edge from vertex $a$ to vertex $c$."},{"iden":"constraints","content":"*   $3 \\leq N \\leq 2000$\n*   $0 \\leq M \\leq 2000$\n*   $1 \\leq u_i ,v_i \\leq N$\n*   $u_i \\neq v_i$\n*   $(u_i,v_i) \\neq (u_j,v_j)$ if $i \\neq j$.\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$\\vdots$\n$u_M$ $v_M$"},{"iden":"sample input 1","content":"4 3\n2 4\n3 1\n4 3"},{"iden":"sample output 1","content":"3\n\nInitially, the condition is not satisfied because, for instance, for vertices $2$, $4$, and $3$, there are directed edges from vertex $2$ to vertex $4$ and from vertex $4$ to vertex $3$, but not from vertex $2$ to vertex $3$.\nYou can make the graph satisfy the condition by adding the following three directed edges:\n\n*   one from vertex $2$ to vertex $3$,\n*   one from vertex $2$ to vertex $1$, and\n*   one from vertex $4$ to vertex $1$.\n\nOn the other hand, the condition cannot be satisfied by adding two or fewer edges, so the answer is $3$."},{"iden":"sample input 2","content":"292 0"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"5 8\n1 2\n2 1\n1 3\n3 1\n1 4\n4 1\n1 5\n5 1"},{"iden":"sample output 3","content":"12"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}