Blackout

AtCoder

IDagc006_f

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

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

Output #3

3

No white cells can be painted black.

API Response (JSON)

{
  "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. Specif...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments