def dfs(v, now):               #now - цвет, в который красим v. равен 1 или 2
    color[v] = now             #собственно, красим v в цвет now
    for to in graph[v]:
        if color[to] == 0:     #если эта вершина еще не покрашена
            dfs(to, 3 - now)   #то запускаем dfs от нее, сменив цвет