{"problem":{"name":"Blackout","description":{"content":"We have a grid with $N$ rows and $N$ columns. The cell at the $i$\\-th row and $j$\\-th column is denoted ($i$, $j$). Initially, $M$ of the cells are painted black, and all other cells are white. Specif","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc006_f"},"statements":[{"statement_type":"Markdown","content":"We have a grid with $N$ rows and $N$ columns. The cell at the $i$\\-th row and $j$\\-th column is denoted ($i$, $j$).\nInitially, $M$ of the cells are painted black, and all other cells are white. Specifically, the cells ($a_1$, $b_1$), ($a_2$, $b_2$), $...$, ($a_M$, $b_M$) are painted black.\nSnuke will try to paint as many white cells black as possible, according to the following rule:\n\n*   If two cells ($x$, $y$) and ($y$, $z$) are both black and a cell ($z$, $x$) is white for integers $1≤x,y,z≤N$, paint the cell ($z$, $x$) black.\n\nFind the number of black cells when no more white cells can be painted black.\n\n## Constraints\n\n*   $1≤N≤10^5$\n*   $1≤M≤10^5$\n*   $1≤a_i,b_i≤N$\n*   All pairs ($a_i$, $b_i$) are distinct.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$:$\n$a_M$ $b_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc006_f","tags":[],"sample_group":[["3 2\n1 2\n2 3","3\n\nIt is possible to paint one white cell black, as follows:\n\n*   Since cells ($1$, $2$) and ($2$, $3$) are both black and a cell ($3$, $1$) is white, paint the cell ($3$, $1$) black."],["2 2\n1 1\n1 2","4\n\nIt is possible to paint two white cells black, as follows:\n\n*   Since cells ($1$, $1$) and ($1$, $2$) are both black and a cell ($2$, $1$) is white, paint the cell ($2$, $1$) black.\n*   Since cells ($2$, $1$) and ($1$, $2$) are both black and a cell ($2$, $2$) is white, paint the cell ($2$, $2$) black."],["4 3\n1 2\n1 3\n4 4","3\n\nNo white cells can be painted black."]],"created_at":"2026-03-03 11:01:14"}}