int cmp(const void* a, const void* b){
    return (*(int**)a)[0] > (*(int**)b)[0];
}

int* gardenNoAdj(int N, int** paths, int pathsSize, int* pathsColSize, int* returnSize){
    int i,j,k,temp,pst,cnt=2;
    for (i = 0; i < pathsSize; i++)
    {
        if (paths[i][0] < paths[i][1])
        {
            temp = paths[i][0];
            paths[i][0] = paths[i][1];
            paths[i][1] = temp;
        }
    }
    qsort(paths, pathsSize, sizeof(int*), cmp);
    int* arr = (int*)malloc(N * sizeof(int));
    for (i = 0; i < N; i++)
        arr[i] = 1;
    
    for (i = 0; i < pathsSize;)
    {
        if (paths[i][0] != cnt)
        {
            arr[cnt - 1] = 1;
        }
        else
        {
            int t[] = { 0, 1, 2, 3, 4 };
            pst = 0;
            while (i < pathsSize && paths[i][0] == cnt && pst<3){
                if (t[arr[paths[i][1] - 1]]){
                    t[arr[paths[i][1] - 1]] = 0;
                    pst++;
                }
                i++;
            }
            for (j = 1; j  < 5; j ++)
            {
                if (t[j]) {
                    arr[cnt - 1] = t[j];
                    break;
                }
            }        
        }
        cnt++;
    }
    *returnSize = N;
    return arr;
}