static edge bi_bfs(const graph& G, node s, node_array<int>& side,
                                           node_array<node>& pred)
{ 
  list<node> Q;

  Q.append(s);
  side[s] = 0;

  while ( ! Q.empty() )
  { node v = Q.head();
    edge e;
    forall_inout_edges(e,v)
    { node w = G.opposite(v,e);
      if (side[v] == side[w]) return e;
      if (side[w] == -1)
      { Q.append(w); 
        pred[w] = v;
        side[w] = 1 - side[v];
       }
     }
    Q.pop();
  }

  return nil;
}


bool Is_Bipartite(const graph& G, list<node>& A, list<node>& B)
{
  node_array<int>  side(G,-1);
  node_array<node> pred(G,nil);
  node v;

  forall_nodes(v,G)
  { if (side[v] != -1) continue;
    edge e = bi_bfs(G,v,side,pred);
    if (e != nil)
    { // construct odd-length circle
      node x = source(e);
      node y = target(e);
      node u;
      for(u=x; u != nil; u = pred[u]) side[u] = -1; 
      for(u = y; side[u] != -1; u = pred[u]) A.append(u);
      A.append(u);
      while (x != u) 
      { A.push(x);
        x = pred[x];
       }
     return false;
    }
   }

  forall_nodes(v,G)
  { if (side[v] == 0) A.append(v);
    if (side[v] == 1) B.append(v);
   }

  return true;

 }