Let k≥2 be an integer. Prove that any k-regular graph contains at least k−1 distinct cycles, all of which have different lengths.

(Note: Cycles that are distinct may share some vertices and/or edges.)