Expected time of handshaking before all hands are painted

There are 1000 people in a hall. One person had his hand painted. Every minute everyone shakes their hand with someone else where we can regard as randomly chosen the 500 pairs of handshaking. What is the expected time (in minutes) needed in order that all hands are painted?

The original problem only asked me the best/worst scenario. Is it possible to solve the expected minutes?

Solving for $n=6$, after $1$ minute, we have $2$ people.

After another expected $1.25$ minutes we have $4$ people, because the probability of a shake with a newbie is $4$ in $5$.

And after another expected $1.25$ minutes, the whole room is full of painted people, because the probability of a shake with a newbie is now $1-0.6\times0.333=0.8$.

So the total expected time is $3$ minutes and $30$ seconds.

But this version doesn't branch, i.e. where there are different numbers of newbies that could be painted, and that requires deeper analysis.

An emulator would be useful here I guess!