AtCoder Grand Contest 006
翻译中…
Problem Statement
翻译中…
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. Specifically, the cells ($a_1$, $b_1$), ($a_2$, $b_2$), $...$, ($a_M$, $b_M$) are painted black.
翻译中…
Snuke will try to paint as many white cells black as possible, according to the following rule:
翻译中…
- 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.
翻译中…
Find the number of black cells when no more white cells can be painted black.
翻译中…
Constraints
翻译中…
$1≤N≤10^5$$1≤M≤10^5$$1≤a_i,b_i≤N$- All pairs (
$a_i$,$b_i$) are distinct.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N M
a_1 b_1
a_2 b_2
:
a_M b_M翻译中…
Output
翻译中…
Print the number of black cells when no more white cells can be painted black.
翻译中…
样例
Input #1
3 2
1 2
2 3
Output #1
3
It is possible to paint one white cell black, as follows:
- Since cells ($1$, $2$) and ($2$, $3$) are both black and a cell ($3$, $1$) is white, paint the cell ($3$, $1$) black.
Input #2
2 2
1 1
1 2
Output #2
4
It is possible to paint two white cells black, as follows:
- Since cells ($1$, $1$) and ($1$, $2$) are both black and a cell ($2$, $1$) is white, paint the cell ($2$, $1$) black.
- Since cells ($2$, $1$) and ($1$, $2$) are both black and a cell ($2$, $2$) is white, paint the cell ($2$, $2$) black.
Input #3
4 3
1 2
1 3
4 4
Output #3
3
No white cells can be painted black.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。