import collections


class Solution(object):
    def gardenNoAdj(self, N, paths):
        """
        :type N: int
        :type paths: List[List[int]]
        :rtype: List[int]
        """
        pd, res, ans = collections.defaultdict(set), [0] * (N + 1), []

        for p in paths:
            pd[p[0]].add(p[1])
            pd[p[1]].add(p[0])

        def backtrack(n):
            if n == N:
                ans.extend(res)
                return True

            if any(res[i] == res[n] for i in pd[n]):
                return False

            if n == 1:
                res[n] = 1

            dif = {1, 2, 3, 4} - set([res[i] for i in pd[n + 1]])
            for c in dif:
                res[n + 1] = c
                if backtrack(n + 1):
                    return True
            return False

        backtrack(0)
        return ans[1:]


if __name__ == '__main__':
    print Solution().gardenNoAdj(3, [[1, 2], [2, 3], [3, 1]])
    print Solution().gardenNoAdj(5, [[4, 1], [4, 2], [4, 3], [2, 5], [1, 2], [1, 5]])
    print Solution().gardenNoAdj(4, [[1, 2], [3, 4]])
    print Solution().gardenNoAdj(4, [[1, 2], [2, 3], [3, 4], [4, 1], [1, 3], [2, 4]])
