Tour

AtCoder

IDabc204_c

Time2000ms

Memory256MB

Difficulty—

The republic of AtCoder has $N$ cities numbered $1$ through $N$ and $M$ roads numbered $1$ through $M$. Road $i$ leads from City $A_i$ to City $B_i$, but you cannot use it to get from City $B_i$ to City $A_i$. Puma is planning her journey where she starts at some city, travels along zero or more roads, and finishes at some city. How many pairs of cities can be the origin and destination of Puma's journey? We distinguish pairs with the same set of cities in different orders. ## Constraints * $2 \leq N \leq 2000$ * $0 \leq M \leq \min(2000,N(N-1))$ * $1 \leq A_i,B_i \leq N$ * $A_i \neq B_i$ * $(A_i,B_i)$ are distinct. * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$ [samples]

Samples

Input #1

Output #1

7

We have seven pairs of cities that can be the origin and destination: $(1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)$.

Input #2

3 0

Output #2

3

We have three pairs of cities that can be the origin and destination: $(1,1),(2,2),(3,3)$.

Input #3

Output #3

16

Every pair of cities can be the origin and destination.

API Response (JSON)

{
  "problem": {
    "name": "Tour",
    "description": {
      "content": "The republic of AtCoder has $N$ cities numbered $1$ through $N$ and $M$ roads numbered $1$ through $M$. Road $i$ leads from City $A_i$ to City $B_i$, but you cannot use it to get from City $B_i$ to Ci",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc204_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The republic of AtCoder has $N$ cities numbered $1$ through $N$ and $M$ roads numbered $1$ through $M$.\nRoad $i$ leads from City $A_i$ to City $B_i$, but you cannot use it to get from City $B_i$ to Ci...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments