題干：

Arseniy is already grown-up and independent. His mother decided to leave him alone for?m?days and left on a vacation. She have prepared a lot of food, left some money and washed all Arseniy's clothes.

Ten minutes before her leave she realized that it would be also useful to prepare instruction of which particular clothes to wear on each of the days she will be absent. Arseniy's family is a bit weird so all the clothes is enumerated. For example, each of Arseniy's?n?socks is assigned a unique integer from?1?to?n. Thus, the only thing his mother had to do was to write down two integers?li?and?ri?for each of the days?— the indices of socks to wear on the day?i?(obviously,?li?stands for the left foot and?ri?for the right). Each sock is painted in one of?k?colors.

When mother already left Arseniy noticed that according to instruction he would wear the socks of different colors on some days. Of course, that is a terrible mistake cause by a rush. Arseniy is a smart boy, and, by some magical coincidence, he posses?k?jars with the paint?— one for each of?k?colors.

Arseniy wants to repaint some of the socks in such a way, that for each of?m?days he can follow the mother's instructions and wear the socks of the same color. As he is going to be very busy these days he will have no time to change the colors of any socks so he has to finalize the colors now.

The new computer game Bota-3 was just realised and Arseniy can't wait to play it. What is the minimum number of socks that need their color to be changed in order to make it possible to follow mother's instructions and wear the socks of the same color during each of?m?days.

Input

The first line of input contains three integers?n,?m?and?k?(2?≤?n?≤?200?000,?0?≤?m?≤?200?000,?1?≤?k?≤?200?000)?— the number of socks, the number of days and the number of available colors respectively.

The second line contain?n?integers?c1,?c2, ...,?cn?(1?≤?ci?≤?k)?— current colors of Arseniy's socks.

Each of the following?m?lines contains two integers?li?and?ri?(1?≤?li,?ri?≤?n,?li?≠?ri)?— indices of socks which Arseniy should wear during the?i-th day.

Output

Print one integer?— the minimum number of socks that should have their colors changed in order to be able to obey the instructions and not make people laugh from watching the socks of different colors.

Examples

Input

3 2 3 1 2 3 1 2 2 3

Output

2

Input

3 2 2 1 1 2 1 2 2 1

Output

0

Note

In the first sample, Arseniy can repaint the first and the third socks to the second color.

In the second sample, there is no need to change any colors.

題目大意：

有n只襪子，m天，k個顏色。（n,m,k<=2e5）

第一行n個數(shù)，代表每只襪子的顏色。接下來m行給出m天中，每天穿的兩只襪子的編號，每只襪子可能不同顏色，現(xiàn)在要讓每天穿的兩只襪子是相同顏色的，要重新染色的襪子數(shù)最少是多少。

解題報告：

直接并查集，然后找出并查集中的顏色最多的襪子是多少，因為并查集后屬于不同集合的元素一定沒有在m天中同時出現(xiàn)過，所以集合之間互不影響，所以這樣做，也不會出現(xiàn)一只襪子被重復染色多次的情況。

因為這里只要最大值，所以不需要對每個集合都先排序然后找最大，而是直接開數(shù)組維護就好了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,m,k; int c[MAX],f[MAX],cnt[MAX]; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v) {int t1 = getf(u),t2 = getf(v);f[t2] = t1; } vector<int> vv[MAX]; int mx,ans; int main() {cin>>n>>m>>k;for(int i = 1; i<=n; i++) scanf("%d",c+i),f[i]=i;for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);merge(u,v);}for(int i = 1; i<=n; i++) getf(i);for(int i = 1; i<=n; i++) {vv[f[i]].pb(c[i]);}for(int i = 1; i<=n; i++) {if(vv[i].size() <= 1) continue;mx = 0;for(auto x : vv[i]) cnt[x]++,mx = max(mx,cnt[x]); for(auto x : vv[i]) cnt[x] = 0;//initans += vv[i].size() - mx;}cout << ans << endl;return 0 ; }

?

總結

以上是生活随笔為你收集整理的【CodeForces - 731C】Socks（并查集，思维）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。