Indiana Jiang and the Temple of Kukulkan

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;

int n, m;
vector<int> used, deg, s;
vector<vector<ii>> gr;
vector<set<ii>> gr2;

set<ii> st;
void create_spanning_tree(int u, int p = -1) {
  used[u] = true;
  deg[u] = p == -1 ? 0 : 1;
  for (auto [to, idx] : gr[u]) if (!used[to]) {
    gr2[u].insert({to, idx});
    gr2[to].insert({u, idx});
    ++deg[u];
    create_spanning_tree(to, u);
  }
  // cout << u+1 << ' ' << deg[u] << '\n';
  if (s[u]) {
    st.insert({deg[u], u});
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  gr.assign(m, vector<ii>());
  gr2.assign(m, set<ii>());

  vector<ii> edges;
  for (int i = 0; i < n; ++i) {
    int a, b; cin >> a >> b, --a, --b;
    edges.push_back({min(a, b), max(a, b)});
    gr[a].push_back({b, i});
    gr[b].push_back({a, i});
  }

  s.assign(m, 0);
  for (int i = 0; i < m; ++i) {
    cin >> s[i];
  }

  vector<int> ans;
  deg.assign(m, 0);
  used.assign(m, false);
  for (int i = 0; i < m; ++i) {
    if (!used[i]) {
      st.clear();

      // cout << "STARTING:\n";
      create_spanning_tree(i);
      // cout << "FINISHING\n";

      if (st.size() % 2 == 1) {
        cout << -1 << '\n';
        return 0;
      }

      while (!st.empty()) {
        auto [dg, u] = *st.begin();
        // cout << u+1 << " = " << dg << '\n';
        st.erase({dg, u});
        if (dg == 1) {
          auto [to, idx] = *gr2[u].begin();
          ans.push_back(idx);
          s[u] = 1 - s[u];
          s[to] = 1 - s[to];
          --deg[to];
          gr2[to].erase({u, idx});
          if (s[to]) {
            st.insert({deg[to], to});
          } else {
            st.erase({1+deg[to], to});
          }
        } else {
          break;
        }
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    // cout << s[i] << ' ';
    if (s[i]) {
      cout << -1 << '\n';
      return 0;
    }
  } // cout << '\n';
  sort(ans.begin(), ans.end());
  ans.erase(unique(ans.begin(), ans.end()), ans.end());
  cout << ans.size() << '\n';
  for (auto a : ans) {
    cout << a+1 << ' ';
  }
  cout << '\n';
}