By every tent they would tell the messenger, ‘Here is food and drink.’ [He was allowed to eat even though it was Yom Kippur]. Between each tent was a mil [2000 amos] , he was walked from tent to tent except the last which was 2 mil until the cliff [which was out of the techum Shabbos].

Yuma 6:6

The messenger would divide up the piece of red wool; half he put on a rock and the other half he tied between the horns of the animal. He then pushed the animal backwards off the cliff. By the time it reached halfway down the hill it was torn limb from limb. He returned to the last tent and stayed there until it got dark.

The messenger and his clothes become tamai as soon as he leaves Yerushalayim. R’ Shimon says he is tamai from the time he pushes the animal off the cliff.