Peaks

AtCoder

IDabc166_c

Time2000ms

Memory256MB

Difficulty—

There are $N$ observatories in AtCoder Hill, called Obs. $1$, Obs. $2$, $...$, Obs. $N$. The elevation of Obs. $i$ is $H_i$. There are also $M$ roads, each connecting two different observatories. Road $j$ connects Obs. $A_j$ and Obs. $B_j$. Obs. $i$ is said to be good when its elevation is higher than those of all observatories that can be reached from Obs. $i$ using just one road. Note that Obs. $i$ is also good when no observatory can be reached from Obs. $i$ using just one road. How many good observatories are there? ## Constraints * $2 \leq N \leq 10^5$ * $1 \leq M \leq 10^5$ * $1 \leq H_i \leq 10^9$ * $1 \leq A_i,B_i \leq N$ * $A_i \neq B_i$ * Multiple roads may connect the same pair of observatories. * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $H_1$ $H_2$ $...$ $H_N$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_M$ $B_M$ [samples]

Samples

Input #1

Output #1

2

*   From Obs. $1$, you can reach Obs. $3$ using just one road. The elevation of Obs. $1$ is not higher than that of Obs. $3$, so Obs. $1$ is not good.
    
*   From Obs. $2$, you can reach Obs. $3$ and $4$ using just one road. The elevation of Obs. $2$ is not higher than that of Obs. $3$, so Obs. $2$ is not good.
    
*   From Obs. $3$, you can reach Obs. $1$ and $2$ using just one road. The elevation of Obs. $3$ is higher than those of Obs. $1$ and $2$, so Obs. $3$ is good.
    
*   From Obs. $4$, you can reach Obs. $2$ using just one road. The elevation of Obs. $4$ is higher than that of Obs. $2$, so Obs. $4$ is good.
    

Thus, the good observatories are Obs. $3$ and $4$, so there are two good observatories.

Input #2

6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Peaks",
    "description": {
      "content": "There are $N$ observatories in AtCoder Hill, called Obs. $1$, Obs. $2$, $...$, Obs. $N$. The elevation of Obs. $i$ is $H_i$. There are also $M$ roads, each connecting two different observatories. Road",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc166_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ observatories in AtCoder Hill, called Obs. $1$, Obs. $2$, $...$, Obs. $N$. The elevation of Obs. $i$ is $H_i$. There are also $M$ roads, each connecting two different observatories. Road...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments