void bfs() {
  queue<pair<int, int>> q;
  forab(i, 1, n + 1) {
      d[i] = {N, -1};
      if (a[i]) {
        q.push({i, a[i]});
        d[i] = {0, a[i]};
        used[i] = 1;
      }
  }
  while (q.size()) {
    int V = q.front().first;
    int val = q.front().second;
    q.pop();
    forn(i, g[V].sz) {
      int to = g[V][i];
      if (a[to] == 0) {
        if (used[to])
            continue;
        else {
            used[to] = 1;
            q.push({to, a[to]});
            d[to].first = d[V].first + 1;
            d[to].second = val;
        }
      }
      else {
        if (used[to]) {
          if (a[to] != val) {
            d[to].first = d[V].first + 1;
            d[to].second = val;
          }
        }
        else {
            used[to] = 1;
            q.push({to, a[to]});
            d[to].first = d[V].first + 1;
            d[to].second = val;
        }
      }
    }
  }
}