<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 A Naive Implementation of the Union-Find Algorithm
Given a set of frozen sets FS this function turns this set into a string that looks like a set of sets.
This function is only used to beautify the output of the union-find algorithm that is shown later.
Step1:  The function $\texttt{arb}(S)$ returns an arbitrary element from the set $S$,
Step2:  Given a set $M$ and a binary relation $R \subseteq M \times M$, the function $\texttt{union_find}$ returns a partition $\mathcal{P}$ of $M$ such that we have
$$ \forall \langle x, y \rangle \in R
Step3:  Given a partition $\mathcal{P}$ of a set $M$ and an element $x$ from $M$, the function $\texttt{find}(x, \mathcal{P})$ 
returns the set $S \in \mathcal{P}$ such that $x \in S$.
<ASSISTANT_TASK:>
Python Code:
def toStr(FS):
    result = '{ '
    for S in FS:
        result += str(set(S)) + ', '
    result = result[:-2]
    result += ' }'
    return result
Explanation: A Naive Implementation of the Union-Find Algorithm
Given a set of frozen sets FS this function turns this set into a string that looks like a set of sets.
This function is only used to beautify the output of the union-find algorithm that is shown later.
End of explanation
def arb(S):
    for x in S:
        return x
Explanation: The function $\texttt{arb}(S)$ returns an arbitrary element from the set $S$,
End of explanation
def union_find(M, R):
    print(f'R = {R}')
    P = { frozenset({x}) for x in M }  # the trivial partition of M
    print(f'P = {toStr(P)}')
    for x, y in R:
        A = find(x, P) # find A
        B = find(y, P) # find B
        if A != B:
            print(f'{x} ≅ {y}: combining {set(A)} and {set(B)}')
            P -= { A,  B }
            P |= { A | B }
            print(f'P = {toStr(P)}')
    return P
Explanation: Given a set $M$ and a binary relation $R \subseteq M \times M$, the function $\texttt{union_find}$ returns a partition $\mathcal{P}$ of $M$ such that we have
$$ \forall \langle x, y \rangle \in R: \exists S \in \mathcal{P}: \bigl(x \in S \wedge y \in S\bigr) $$
It works by starting with the trivial partition 
$$\mathcal{P} := \bigl{ { x } \mid x \in M \bigr}. $$
As long as there is a pair $\langle x, y \rangle \in R$ such that:
* $x \in A$, $y \in B$, where $A \in \mathcal{P}$ and $B \in \mathcal{P}$, 
* but $A \not= B$
we update the partition $\mathcal{P}$ as follows:
$$ \mathcal{P} := \mathcal{P} \backslash { A, B } \cup { A \cup B }. $$
End of explanation
def find(x, P):
    return arb({ S for S in P if x in S })
def demo():
    M = set(range(1, 9+1))
    R = { (1, 4), (7, 9), (3, 5), (2, 6), (5, 8), (1, 9), (4, 7) }
    P = union_find(M, R)
demo()
Explanation: Given a partition $\mathcal{P}$ of a set $M$ and an element $x$ from $M$, the function $\texttt{find}(x, \mathcal{P})$ 
returns the set $S \in \mathcal{P}$ such that $x \in S$.
End of explanation
<END_TASK>