409357: GYM103488 K Klee and Bomb
Description
Klee is developing a new type of bomb called Peng Peng Bomb!
There are $$$n$$$ bombs numbered from $$$1$$$ to $$$n$$$, bomb $$$i$$$ has color $$$c_i$$$. The $$$n$$$ bombs are connected with $$$m$$$ links, each link connects two different bombs. Bomb $$$x$$$ will explode if meets one of the following conditions:
- $$$x$$$ is on fire by Klee.
- Bomb $$$y$$$ connected to $$$x$$$ and of the same color as $$$x$$$ explodes. Formally, there exists a link between $$$x$$$ and $$$y$$$, and $$$c_x = c_y$$$ holds.
Please help Klee find the maximum number of bombs can be exploded.
The first line of input contains two integers $$$n(1\le n\le 3\times 10^5)$$$ and $$$m(0\le m\le 3\times 10^5)$$$ — the number of bombs and links respectively.
The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n(1\le c_i\le n)$$$ — the color of each bomb.
In the next $$$m$$$ lines, each line contains two integers $$$u, v(1\le u,v\le n, u\ne v)$$$ — two bombs which is connected by the link.
It is guaranteed that for any pair of bombs $$$(x, y)$$$, there are at most $$$1$$$ link between them.
OutputYou should output an integer — the maximum number of bombs can be exploded.
ExamplesInput5 3 1 1 2 1 2 1 2 2 3 3 4Output
4Input
4 6 1 2 1 2 1 2 2 3 3 4 4 1 1 3 2 4Output
3Note
In the example $$$1$$$, if you change $$$c_3$$$ to $$$1$$$ and Klee choose any one of $$$[1,2,3,4]$$$ to be on fire, $$$4$$$ bombs will explode.