class Solution:
    def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
        ret = [1]*N
        dc = collections.defaultdict(list)
        for p in paths:
            dc[max(p)].append(min(p))

        for k in sorted(dc):
            ret[k-1] = ({1,2,3,4} - {ret[vv-1] for vv in dc[k]}).pop()
        return ret