CF1515D Phoenix and Socks

To satisfy his love of matching socks, Phoenix has brought his $ n $ socks ( $ n $ is even) to the sock store. Each of his socks has a color $ c_i $ and is either a left sock or right sock. Phoenix can pay one dollar to the sock store to either: - recolor a sock to any color $ c' $ $ (1 \le c' \le n) $ - turn a left sock into a right sock - turn a right sock into a left sock The sock store may perform each of these changes any number of times. Note that the color of a left sock doesn't change when it turns into a right sock, and vice versa. A matching pair of socks is a left and right sock with the same color. What is the minimum cost for Phoenix to make $ n/2 $ matching pairs? Each sock must be included in exactly one matching pair.

N/A

N/A

In the first test case, Phoenix can pay $ 2 $ dollars to: - recolor sock $ 1 $ to color $ 2 $ - recolor sock $ 3 $ to color $ 2 $ There are now $ 3 $ matching pairs. For example, pairs $ (1, 4) $ , $ (2, 5) $ , and $ (3, 6) $ are matching.In the second test case, Phoenix can pay $ 3 $ dollars to: - turn sock $ 6 $ from a right sock to a left sock - recolor sock $ 3 $ to color $ 1 $ - recolor sock $ 4 $ to color $ 1 $ There are now $ 3 $ matching pairs. For example, pairs $ (1, 3) $ , $ (2, 4) $ , and $ (5, 6) $ are matching.