$$$\qquad$$$Во Вселенной Адамса существует $$$N$$$ планет, пронумерованных от $$$1$$$ до $$$N$$$. Планеты соединены космическими лифтами в количестве $$$N-1$$$. $$$i$$$-тый космический лифт $$$(1 \leq i \leq N-1)$$$ соединяет планету $$$A_i$$$ с планетой $$$B_i$$$. На каждом космическом лифте можно двигаться в любом направлении. Вы можете попасть с любой планеты на любую другую планету используя космические лифты.

$$$\qquad$$$В настоящее время Вселенная Адамса разделена на $$$K$$$ галактик, пронумерованных от $$$1$$$ до $$$K$$$. Планета $$$j$$$ $$$(1 \leq j \leq N)$$$ относится к галактике $$$C_j$$$. К каждой галактике относится минимум одна планета.

$$$\qquad$$$Одна из галактик будет выбрана Старшим Координатором Библброкосом в качестве главного транспортного узла (ГТУ). По причинам государственной безопасности, ГТУ должен соответствовать следующим условиям.

$$$\qquad$$$Должно быть возможно попасть с любой планеты ГТУ на любую другую планету ГТУ проходя только планеты, которые относятся к ГТУ.

$$$\qquad$$$Тем не менее, Старший Координатор Библброкс заметил, что может существовать случай, когда ни одна из галактик Вселенной Адамса не удовлетворяет данному условию, и он не сможет выбрать ГТУ.

$$$\qquad$$$Для того, чтобы решить данную проблему, Старший Координатор Библброкс может объединять галактики. А именно может выполнять следующую операцию.

$$$\qquad$$$Выбрать $$$x$$$ и $$$y$$$ удовлетворяющие условию $$$(1 \leq x, y \leq K)$$$ и $$$x \neq y$$$ и менять планеты галактик так, что планеты галактики $$$y$$$ станут планетами галактики $$$x$$$.

$$$\qquad$$$Так как объединение галактик — это крайне трудозатратно, Старший Координатор Библброкс хочет минимизировать количество объединений, для выбора ГТУ.

$$$\qquad$$$Так как Библброкс координирует всю Вселенную Адамса, что является крайне непростой задачей, он не сможет справиться с этим самостоятельно и поэтому обратился к вам за помощью. Вычислите минимальное количество объединений галактик для выбора ГТУ.