English · Original
Chinese · Translation
Formal · Original
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 _l__i_ and _r__i_ for each of the days — the indices of socks to wear on the day _i_ (obviously, _l__i_ stands for the left foot and _r__i_ 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 _c_1, _c_2, ..., _c__n_ (1 ≤ _c__i_ ≤ _k_) — current colors of Arseniy's socks.
Each of the following _m_ lines contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_, _r__i_ ≤ _n_, _l__i_ ≠ _r__i_) — 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.
[samples]
## 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.
Arseniy 已经长大独立了。他的母亲决定离开他 #cf_span[m] 天去度假，临走前为他准备了大量食物、一些钱，并洗好了他所有的衣服。
在离开前十分钟，她意识到最好为每一天指定具体该穿哪双袜子。Arseniy 的家庭有些奇特，因此所有衣服都有编号。例如，Arseniy 的 #cf_span[n] 双袜子分别被赋予从 #cf_span[1] 到 #cf_span[n] 的唯一整数。因此，他母亲只需为每一天写下两个整数 #cf_span[li] 和 #cf_span[ri] —— 表示第 #cf_span[i] 天应穿的左脚和右脚袜子的编号（显然，#cf_span[li] 对应左脚，#cf_span[ri] 对应右脚）。每双袜子被染成 #cf_span[k] 种颜色之一。
母亲离开后，Arseniy 发现根据这份说明，他有些日子会穿上颜色不同的袜子。这显然是由于匆忙造成的错误。但 Arseniy 是个聪明的男孩，巧合的是，他拥有 #cf_span[k] 个颜料罐——每种颜色一个。
Arseniy 希望重新染一些袜子，使得在 #cf_span[m] 天中，每天都能按照母亲的指示穿上颜色相同的袜子。由于他接下来几天会非常忙，没有时间再更改袜子颜色，所以他必须现在就确定好颜色。
新的电脑游戏 Bota-3 刚刚发布，Arseniy 急不可耐地想玩。请问，最少需要改变多少双袜子的颜色，才能满足母亲的指令，使得每天穿的两只袜子颜色相同？
输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200 000], #cf_span[0 ≤ m ≤ 200 000], #cf_span[1 ≤ k ≤ 200 000]）—— 分别表示袜子数量、天数和可用颜色数量。
第二行包含 #cf_span[n] 个整数 #cf_span[c1], #cf_span[c2], ..., #cf_span[cn]（#cf_span[1 ≤ ci ≤ k]）—— 表示 Arseniy 袜子的当前颜色。
接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li, ri ≤ n], #cf_span[li ≠ ri]）—— 表示第 #cf_span[i] 天应穿的袜子编号。
请输出一个整数——为满足指令、避免因穿不同颜色袜子而被人笑话，最少需要改变颜色的袜子数量。
在第一个样例中，Arseniy 可以将第一双和第三双袜子都染成第二种颜色。
在第二个样例中，无需更改任何颜色。
## Input
输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200 000], #cf_span[0 ≤ m ≤ 200 000], #cf_span[1 ≤ k ≤ 200 000]）—— 分别表示袜子数量、天数和可用颜色数量。第二行包含 #cf_span[n] 个整数 #cf_span[c1], #cf_span[c2], ..., #cf_span[cn]（#cf_span[1 ≤ ci ≤ k]）—— 表示 Arseniy 袜子的当前颜色。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li, ri ≤ n], #cf_span[li ≠ ri]）—— 表示第 #cf_span[i] 天应穿的袜子编号。
## Output
请输出一个整数——为满足指令、避免因穿不同颜色袜子而被人笑话，最少需要改变颜色的袜子数量。
[samples]
## Note
在第一个样例中，Arseniy 可以将第一双和第三双袜子都染成第二种颜色。在第二个样例中，无需更改任何颜色。
Let $ n $, $ m $, $ k $ be given integers.
Let $ c = [c_1, c_2, \dots, c_n] $ be the array of current colors of socks, where $ c_i \in \{1, 2, \dots, k\} $ is the color of sock $ i $.
Let $ D = \{(l_i, r_i) \mid 1 \leq i \leq m\} $ be the set of $ m $ pairs of sock indices that must be worn together on each day.
Define an undirected graph $ G = (V, E) $ where:
- $ V = \{1, 2, \dots, n\} $ (socks as vertices),
- $ E = \{(l_i, r_i) \mid (l_i, r_i) \in D\} $ (edges connect socks worn together on the same day).
Let $ \mathcal{C} $ be the set of connected components of $ G $.
For each connected component $ C \in \mathcal{C} $, let:
- $ S_C $ be the multiset of current colors of socks in $ C $,
- $ f_C(x) $ be the frequency of color $ x $ in $ S_C $,
- $ \text{max}_C = \max_{x \in \{1,\dots,k\}} f_C(x) $ be the maximum frequency of any single color in $ C $,
- $ |C| $ be the number of socks in component $ C $.
The minimum number of color changes required for component $ C $ is $ |C| - \text{max}_C $, since we repaint all socks to the most frequent color in $ C $ to minimize changes.
The total minimum number of color changes is:
$$
\sum_{C \in \mathcal{C}} (|C| - \text{max}_C)
$$
API Response (JSON)
{
"problem": {
"name": "C. Socks",
"description": {
"content": "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 clothe",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF731C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 clothe...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Arseniy 已经长大独立了。他的母亲决定离开他 #cf_span[m] 天去度假，临走前为他准备了大量食物、一些钱，并洗好了他所有的衣服。\n\n在离开前十分钟，她意识到最好为每一天指定具体该穿哪双袜子。Arseniy 的家庭有些奇特，因此所有衣服都有编号。例如，Arseniy 的 #cf_span[n] 双袜子分别被赋予从 #cf_span[1] 到 #cf_span[n] 的唯一整数。因此，他...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $, $ m $, $ k $ be given integers.\n\nLet $ c = [c_1, c_2, \\dots, c_n] $ be the array of current colors of socks, where $ c_i \\in \\{1, 2, \\dots, k\\} $ is the color of sock $ i $.\n\nLet $ D = \\{(l...",
"is_translate": false,
"language": "Formal"
}
]
}