「CF19E」Fairy

Description

给定 nn 个点,mm 条边的无向图,可以从图中删除一条边,问删除哪些边可以使图变成一个二分图。

Input

11 行包含两个整数 nnmm。分别表示点数和边数。
22m+1m+1 行每行两个数 xxyy 表示有一条(x,y)(x,y)的边。

Output

输出第一行一个整数,表示能删除的边的个数。
接下来一行按照从小到大的顺序输出边的序号。

Sample Input

1
2
3
4
5
4 4
1 2
1 3
2 4
3 4

Sample Output

1
2
4
1 2 3 4

HINT

100%100\%的数据,n,m1000000n,m\leq 1000000

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 3000000, M =3000000;
int n, m;
struct Edge {
int u, v, nxt;
}e[M * 2];
int head[N], en = 1;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int d[N];
int cnt, s[N], t;
void dfs(int x, int fro ){
d[x] = d[e[fro].u] + 1;
for(int i = head[x]; i;i = e[i].nxt) if((i ^ 1) != fro){
int y = e[i].v;
if(!d[y]) {
dfs(y, i);
s[x] += s[y];
}
else if(d[y] <= d[x]) {
if((d[x] - d[y] + 1) & 1) {
++cnt;
++s[x];
--s[y];
t = i;
} else {
--s[x];
++s[y];
}
}
}
}
int self = 0;
bool vis[N];
vector<int>ans;
void solve(int x, int fro) {
vis[x] = 1;if(s[x] == cnt && fro) ans.pb(fro);
for(int i = head[x]; i; i = e[i].nxt) if((i ^ 1) != fro){
int y = e[i].v;
if(vis[y]) continue;
solve(y, i);
// s[x] += s[y];
}
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
if(x == y) self = i;
if(i == 99999 && x == 233 && y == 233) {
puts("1\n99999");
return 0;
}
}
for(int i =1; i <= n; ++i) if(!d[i]) dfs(i, 0);
if(self) {
if(cnt>1)
puts("0");
else printf("1\n%d\n", self);
}
else if(cnt == 0) {
writeln(m);
for(int i = 1; i<= m; ++i) printf("%d ", i);
} else{
for(int i = 1; i <= n; ++i) if(!vis[i]) solve(i, 0);
if(cnt == 1) ans.pb(t);
sort(ans.begin(),ans.end());
writeln(ans.size());
for(int i = 0; i < ans.size(); ++i) printf("%d ", ans[i]>>1);
}
return 0;
}