Complexity of determining unique elements of each cycle in a permutation
Even for $k=2$ when the instance may have two cycles of length $n/2$, 
any sublinear algorithm can only build chains of length $\ll n/4$, so no deterministic algorithm can guarantee that the two vertices it outputs belong to distinct cycles. 

I doubt (though I am not sure and do not have a proof) that the problem would admit a solution in sublinear expected time even for algorithms with probabilistic guarantees.