Magician

AtCoder

IDrelay_g

Time2000ms

Memory256MB

Difficulty—

You have $N$ cups and $1$ ball. The cups are arranged in a row, from left to right. You turned down all the cups, then inserted the ball into the leftmost cup. Then, you will perform the following $Q$ operations: * The $i$\-th operation: swap the positions of the $A_i$\-th and $B_i$\-th cups from the left. If one of these cups contains the ball, the ball will also move. Since you are a magician, you can cast a magic described below: * Magic: When the ball is contained in the $i$\-th cup from the left, teleport the ball into the adjacent cup (that is, the $(i-1)$\-th or $(i+1)$\-th cup, if they exist). The magic can be cast before the first operation, between two operations, or after the last operation, but you are allowed to cast it at most once during the whole process. Find the number of cups with a possibility of containing the ball after all the operations and possibly casting the magic. ## Constraints * $2 \leq N \leq 10^5$ * $1 \leq Q \leq 10^5$ * $1 \leq A_i < B_i \leq N$ ## Input The input is given from Standard Input in the following format: $N$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_Q$ $B_Q$ [samples]

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Magician",
    "description": {
      "content": "You have $N$ cups and $1$ ball. The cups are arranged in a row, from left to right. You turned down all the cups, then inserted the ball into the leftmost cup. Then, you will perform the following $Q$",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "relay_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have $N$ cups and $1$ ball.\nThe cups are arranged in a row, from left to right.\nYou turned down all the cups, then inserted the ball into the leftmost cup.\nThen, you will perform the following $Q$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments