long long color[2000000];
//連結グラフなら1回でok
//cは0以外ならなんでも
bool bipartite_check(const vector<vector<long long>> &G, long long v, long long c)
{
    color[v] = c;
    for (long long nv : G[v])
    {
        if (color[nv] == c)
            return false;
        if (color[nv] == 0)
        {
            if (!bipartite_check(G, nv, -c))
                return false;
        }
    }
    return true;
}