{"problem":{"name":"Transitivity","description":{"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$. You may perform the follow","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc292_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc292_e","tags":[],"sample_group":[["4 3\n2 4\n3 1\n4 3","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$."],["292 0","0"],["5 8\n1 2\n2 1\n1 3\n3 1\n1 4\n4 1\n1 5\n5 1","12"]],"created_at":"2026-03-03 11:01:14"}}