You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 &lt;= i &lt;= n-1 where source[i] != target[i] (0-indexed).

Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

&nbsp;
Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: source can be transformed the following way:
- Swap indices 0 and 1: source = [2,1,3,4]
- Swap indices 2 and 3: source = [2,1,4,3]
The Hamming distance of source and target is 1 as they differ in 1 position: index 3.


Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Explanation: There are no allowed swaps.
The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.


Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0


&nbsp;
Constraints:


	n == source.length == target.length
	1 &lt;= n &lt;= 105
	1 &lt;= source[i], target[i] &lt;= 105
	0 &lt;= allowedSwaps.length &lt;= 105
	allowedSwaps[i].length == 2
	0 &lt;= ai, bi &lt;= n - 1
	ai != bi


class UnionFind:
    def __init__(self, n):
        self.roots = [i for i in range(n)]

    def find(self, v):
        if self.roots[v] != v:
            self.roots[v] = self.find(self.roots[v])

        return self.roots[v]

    def union(self, u, v):
        self.roots[self.find(u)] = self.find(v)

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        uf = UnionFind(len(source))
        for idx1, idx2 in allowedSwaps:
            uf.union(idx1, idx2)

        m = collections.defaultdict(set)
        for i in range(len(source)):
            m[uf.find(i)].add(i)

        res = 0
        for indices in m.values():
            freq = {}
            for i in indices:
                freq[source[i]] = freq.get(source[i], 0)+1
                freq[target[i]] = freq.get(target[i], 0)-1
            res += sum(val for val in freq.values() if val > 0)

        return res
class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int minHamming = 0;
        UnionFind uf = new UnionFind(source.length);
        for (int [] swap : allowedSwaps) {
            int firstIndex = swap[0];
            int secondIndex = swap[1];
           // int firstParent = uf.find(firstIndex);
           // int secondParent = uf.find(secondIndex);
           // if (firstParent != secondParent)
           //     uf.parent[firstParent] = secondParent;
		   uf.union(firstIndex, secondIndex);
        }
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for (int i=0; i<source.length; i++) {
            int num = source[i];
            int root = uf.find(i);
            map.putIfAbsent(root, new HashMap<>());
            Map<Integer, Integer> store = map.get(root);
            store.put(num, store.getOrDefault(num, 0) + 1);
        }
        for (int i=0; i<source.length; i++) {
            int num = target[i];
            int root = uf.find(i);
            Map<Integer, Integer> store = map.get(root);
            if (store.getOrDefault(num, 0) == 0)
                minHamming += 1;
            else
                store.put(num, store.get(num) - 1);
        }
        return minHamming;
    }
}

class UnionFind {
    int size;
    int components;
    int [] parent;
    int [] rank;
    UnionFind(int n) {
        if (n <= 0) throw new IllegalArgumentException("Size <= 0 is not allowed");
        size = n;
        components = n;
        parent = new int [n];
        rank = new int [n];
        for (int i=0; i<n; i++)
            parent[i] = i;
    }
    
    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
    
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rank[rootQ] > rank[rootP]) {
            parent[rootP] = rootQ;
        }
        else {
            parent[rootQ] = rootP;
            if (rank[rootQ] == rank[rootP])
                rank[rootP] += 1;
        }
        components -= 1;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
    
    public int numberComponents() {
        return components;
    }
}
class Solution {
public:
    vector<int> parents;
    vector<int> ranks;
    int find(int a) {
        if (a == parents[a])
            return parents[a];
        return parents[a] = find(parents[a]);
    }

    void uni(int a, int b) {
        a = find(a);
        b = find(b);

        if (ranks[a] >= ranks[b]) {
            parents[b] = a;
            ranks[a]++;
        }
        else {
            parents[a] = b;
            ranks[b]++;
        }
    }

    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        ranks = vector<int>(n, 0);

        for (int i = 0; i < n; i++) {
            parents.push_back(i);
        }

        for (auto &v : allowedSwaps)
            uni(v[0], v[1]);
        vector<unordered_multiset<int>> subs(n);

        for (int i = 0; i < n; i++) {
            subs[find(i)].insert(source[i]);
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!subs[parents[i]].count(target[i]))
                cnt++;
            else
                subs[parents[i]].erase(subs[parents[i]].find(target[i]));
        }
        return cnt;
    }
};
var minimumHammingDistance = function(source, target, allowedSwaps) {
    const n = source.length;
    
    const uf = {};
    const sizes = {};
    const members = {};
    
    // initial setup
    for (let i = 0; i < n; i++) {
        const srcNum = source[i];
        
        uf[i] = i;
        sizes[i] = 1;
        members[i] = new Map();
        members[i].set(srcNum, 1);
    }
    
    function find(x) {
        if (uf[x] != x) uf[x] = find(uf[x]);
        return uf[x];
    }
    
    function union(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        
        if (rootX === rootY) return;
        
        if (sizes[rootX] > sizes[rootY]) {
            uf[rootY] = rootX;
            sizes[rootX] += sizes[rootY];
            
            for (const [num, count] of members[rootY]) {
                if (!members[rootX].has(num)) members[rootX].set(num, 0);
                members[rootX].set(num, members[rootX].get(num) + count);
            }
        }
        else {
            uf[rootX] = rootY;
            sizes[rootY] += sizes[rootX];

            const num = source[x];

            for (const [num, count] of members[rootX]) {
                if (!members[rootY].has(num)) members[rootY].set(num, 0);
                members[rootY].set(num, members[rootY].get(num) + count);
            }
        }
    }
    
    for (const [idx1, idx2] of allowedSwaps) {
        union(idx1, idx2);
    }
    
    let mismatches = 0;
    
    for (let i = 0; i < n; i++) {
        const srcNum = source[i];
        const tarNum = target[i];
        
        const group = find(i);
        
        if (members[group].has(tarNum)) {
            members[group].set(tarNum, members[group].get(tarNum) - 1);
            if (members[group].get(tarNum) === 0) members[group].delete(tarNum);
        }   
        else {
            mismatches++;
        }
    }
    
    return mismatches;
};
Minimize Hamming Distance After Swap Operations