List coloring

Given is an array S that represents the successors in a linked list: a list 2 -> 3 -> 0 -> 4 -> 5 -> 1 is represented by an array
i 012345
S[i] 423051
The task is to color the elements with three colors such that each v has different color than p[v], e.g. to produce an array C:
i 012345
C[i] 010110

Here is an algorithm that works in time O(log*n) and work O(n log*n): 

input int S[_];
int n=S.size;
output int C[n];

pardo(i:n) C[i]=i;

for (int t=n;t>1;t=log(t))
pardo(i:n) {
  int pos = (C[i]~C[S[i]])~|;
  int bit=0;
  if (C[i]&(2^pos)) bit=1;
  C[i]=2*pos+bit;
}

int P[n];
pardo(i:n) P[S[i]]=i;

for (int c=3;c<6;c++)
pardo(i:n)
if (C[i]==c) {
  int u[3];
  pardo(j:3)u[j]=0;
  if (C[S[i]]<3) u[C[S[i]]]=1;
  if (C[P[i]]<3) u[C[P[i]]]=1;
  int k=0;
  while(u[k]==1)k++;
  C[i]=k;
}