class Solution:
   # 整体思路采用BFS方法,还需考虑不连通图的问题,然后着手结果唯一
   def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
     #构建一个answer数组
     answer = [0 for _ in range(N)]
     #构建所有节点
     all_nodes = []
     [all_nodes.append(i) for i in range(1,N+1)]
     #构建visted列表
     visted = dict.fromkeys(all_nodes, 0)
     #初始化nei字典元素为空列表
     nei = [[] for _ in range(N)]
     # 构建无向邻接表，无邻居则不构建
     for path in paths:
       nei[path[0]-1].append(path[1])
       nei[path[1]-1].append(path[0])
     #遍历每一个点，每个点保证自己邻接点不是和自己相同就行
     answer[0] = 1 
     for node in range(1,N+1):  #遍历所有节点
       visted[node] = 1
       fix = set()
       if(answer[node-1]==0): #如果为0,说明不是连通图
         answer[node-1] = 1 
       flowers=[1,2,3,4]
       nei[node-1] = sorted(nei[node-1]) #排序邻居节点
       flowers.pop(answer[node-1]-1) #弹出父节点的flowers
       for sinode in nei[node-1]: #遍历邻居
         if(visted[sinode] == 0): #如果邻居未被访问过
           answer[sinode-1] = flowers[0] #使用1,弹出1
           flowers.pop(0)
         else: #如果邻居被访问过
           if(answer[sinode-1]==answer[node-1]):
             answer[node-1] = flowers[0] 
             flowers.pop(0) 
           fix.add(answer[sinode-1])
       if not fix:
         continue
       else:
         flowers=[1,2,3,4]
         for a_val in list(fix):
           flowers.remove(a_val)
         answer[node-1] = flowers[0]
             
     return answer
 

class Solution:
  def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
   #构建一个answer数组
    answer = [0]*N
    #初始化nei字典元素为空列表
    nei = [[] for _ in range(N)]
    # 构建无向邻接表，无邻居则不构建
    for path in paths:
      nei[path[0]-1].append(path[1])
      nei[path[1]-1].append(path[0])
    for node in range(1,N+1):  #遍历所有节点
      flowers={1,2,3,4}
      #临时存储邻居含有的花类型
      a = set()
      for sinode in nei[node-1]: #遍历邻居
        a.add(answer[sinode-1])
      flowers = flowers - a 
      answer[node-1] = flowers.pop()
                
    return answer