US-TST 2016 Problem 1

Let $S=\{1, \ldots, n\}$. Given a bijection $f: S \rightarrow S$ an orbit of $f$ is a set of the form $\{x, f(x), f(f(x)), \ldots\}$ for some $x \in S$. We denote by $c(f)$ the number of distinct orbits of $f$. For example, if $n=3$ and $f(1)=2, f(2)=1, f(3)=3$, the two orbits are $\{1,2\}$ and $\{3\}$, hence $c(f)=2$. Given $k$ bijections $f_{1}, \ldots, f_{k}$ from $S$ to itself, prove that $$c\left(f_{1}\right)+\cdots+c\left(f_{k}\right) \leq n(k-1)+c(f)$$ where $f: S \rightarrow S$ is the composed function $f_{1} \circ \cdots \circ f_{k}$.