题意

给定 nnn 个点，mmm 条边，保证没有自环，且图连通。对于每个点有一个期望度数d[i]d[i]d[i]，−1≤d[i]≤1-1\leq d[i]\leq1−1≤d[i]≤1。询问是否能保存图中的一些边使得所有点的度数的奇偶性与期望度数的奇偶性相同。（当 d[i]=−1d[i] = -1d[i]=−1 时点 iii 的度数为任意都可以）。

思路

首先需要知道：
（1）因为增加一条边，图的总度数就会增加 222，因此图中的总度数总是为偶数。所以当图中点的 期望度数和 为奇数时 且 没有 d[i]=−1d[i] = -1d[i]=−1 的点时无解。
（2）而有 d[i]=−1d[i] = -1d[i]=−1 的点时我们可以通过调整与 −1-1−1 的点的连边来调整图中点的度数，当删去一条与 −1-1−1 点的连边时，−1-1−1 的点的度数变化可以不用考虑，以此达到调整度数的目的。

考虑使用 dfs，因为保证图是连通的，所以从任意根节点向下搜(当总度数为奇数时从 d[i]=−1d[i] = -1d[i]=−1 的点开始搜)，每次保证除了根以外的子树所有顶点都符合 ddd 度数要求，而最终返回到整棵树的根时，所有点的期望度数已经符合。

使用dfs的正确性证明（返回到根时根的度数期望也被满足的证明）：
当期望总度数为奇数时，我们以 −1-1−1 节点为根，那么返回到根时根的度数已经无关重要了。
当期望总度数为偶数时，
1.以奇数度数期望的节点为根，那么除了根节点以外其他点的期望度数被满足时，度数之和肯定也是奇数，我们在 dfs 过程中是以增加边来调节度数的，所以总度数肯定为偶数，那么说明肯定有奇数条边连接在了根上，所以根的期望度数为奇数也得到了保证。
2.以偶数度数期望的节点为根，同理当调整完其余度数后图的总度数为偶数，除根以外的所有点度数也为偶数，根的度数自然也为偶数。

代码

#include 
using namespace std;
const int N = 3e5 + 10;
int d[N];
struct edge{int to, nex;
}e[N * 2];
int head[N], tot = 1, cnt;
void add(int to, int from){e[++ tot].to = to;e[tot].nex = head[from];head[from] = tot;
}
bool Edge[N * 2];
int vis[N], d[N], n, m;int dfs(int u){/*res 代表自己期望度数奇偶性，若是增加的边的数量与之奇偶性相同，那么res = 0, 否则 res = 1所以 res 是用来说明自身的期望奇偶性有没有满足的。初始没有边，所以偶数的期望度数 = 0 也代表着最开始就被满足，奇数也代表不满足*/int res = d[u]; for(int i = head[u]; i; i = e[i].nex){int v = e[i].to;if(vis[v]) continue ;if(dfs(v)) {Edge[i] = Edge[i ^ 1] = 1; //增加该边标记res ^= 1; //增加一条边 期望度数是否被满足发生改变}}if(d[u] == -1) res = 0;//-1 的期望度数一定被满足return res;
}
int main(){ios::sync_with_stdio(false);cout.tie(NULL);cin >> n >> m;int id = 0, sum = 0;for(int i = 1; i <= n; i ++){cin >> d[i];if(d[i] == -1) id = i;else sum ^= d[i];}for(int i = 1; i <= m; i ++){int u, v;cin >> u >> v; add(u, v);add(v, u);}if((sum & 1) && !id){cout << "-1";return 0;}dfs(max(1, id)); // -1 点存在就都从 -1 点开始cout << cnt << "\n";for(int i = 2; i <= 2 * m + 1; i += 2){if(Edge[i]) cout << (i / 2) << "\n";}return 0;
}