Proving that the cardinality of a set is even 
Let $E$ be a set and $f:E\to E$ be a function such that $f\circ f=Id$.
Let $A=\{x\in E, f(x)\neq x\}$.
Suppose that $A$ is finite.
Prove that the cardinality of $A$ is even.

My idea is to rewrite $A$ as a disjoint union of sets with even cardinality, but I've been unsuccessful so far.
I noticed that $f$ acts as a permutation over the elements of $A$.
What should I do next ?
 A: For each $a\in A$ let $S_a=\{a,f(a)\}$. 
1) Show that $|S_a|=2$ for all $a\in A$. 
2) Show that $S_a\cap S_b\ne \emptyset$ implies $S_a=S_b$, for all $a,b\in A$. 
3) Count the number of elements in $A=\bigcup_{a\in A}S_a$.
In a bit more sophisticated language, there is an action of $\mathbb Z_2$ on $A$ given by applying $f$. The orbits are the $S_a$. By definition, all stablizers are trivial, and thus all orbits have size $|\mathbb Z_2|=2$. The entire set $A$ is the disjoint union of orbits, and thus even. 
A: $f|_A:A \longrightarrow A$ permutes all elements of $A$ and has no fixed points and $f^2 = id_A$.
I want to prove that if $S\subseteq A$ and $f$ permutes the elements of $S$, then the cardinality of $S$ is even. Taking $S=A$ we get the thesis.
I work by contradiction. Suppose there exists $S \subseteq A$ such that $f$ permutes the points of $S$ and $S$ has odd cardinality. Then you can consider such a set with minimal (odd) cardinality.
Clearly, since the cardinality of $S$ is odd, we have $S \neq \emptyset$.
But now, pick $x \in S$. Then $S'=S \setminus \{ x, f(x)\}$ has odd cardinality and $f$ permutes all elements of $S'$, contradicting the minimality of $S$. 
