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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include <bits/stdc++.h>
#define FAST_IO
#ifdef FAST_IO
const int IN_LEN = 100000, OUT_LEN = 100000;
inline int nextChar() {
static char buf[IN_LEN], *h, *t;
if (h == t) {
t = (h = buf) + fread(buf, 1, IN_LEN, stdin);
if (h == t) return -1;
}
return *h++;
}
template<class T>
inline bool read(T &x) {
static bool iosig = 0;
static char c;
for (iosig = 0, c = nextChar(); !isdigit(c); c = nextChar()) {
if (c == -1) return false;
if (c == '-') iosig = 1;
}
for (x = 0; isdigit(c); c = nextChar()) x = (x << 1) + (x << 3) + (c ^ '0');
if (iosig) x = -x;
return true;
}
char obuf[OUT_LEN], *oh = obuf;
inline void writeChar(const char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
template<class T>
inline void write(T x) {
static int buf[30], cnt;
if (!x) writeChar(48);
else {
if (x < 0) writeChar('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) writeChar(buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
#endif
const int MAXN = 100005;
const int MAXM = MAXN << 2;
int n, m, head[MAXN], tot = 1, next[MAXM], to[MAXM];
bool vis[MAXM];
int cnt, tour[MAXM];
inline void addEdge(const int u, const int v) { (++tot)[next] = head[u], (head[u] = tot)[to] = v; }
int deg[MAXN];
namespace DirectedGraph {
inline void dfs(const int u) {
register int &e = head[u];
while (e) {
if (vis[e]) e = e[next];
else {
register int id = e - 1;
vis[e] = true, dfs(e[to]), tour[++cnt] = id;
}
}
}
inline bool solve() {
read(n), read(m);
register int u, v;
while (m--) read(u), read(v), addEdge(u, v), deg[u]--, deg[v]++;
for (register int u = 1; u <= n; u++) if (deg[u]) return false;
for (register int u = 1; u <= n; u++) {
if (head[u]) {
dfs(u);
break;
}
}
for (register int u = 1; u <= n; u++) if (head[u]) return false;
return true;
}
}
namespace UndirectedGraph {
inline int getEdgeId(const int &e) {
register int id = e >> 1;
return e & 1 ? -id : id;
}
inline void dfs(const int u) {
register int &e = head[u];
while (e) {
if (vis[e]) e = e[next];
else {
register int id = getEdgeId(e);
vis[e] = vis[e ^ 1] = true, dfs(e[to]), tour[++cnt] = id;
}
}
}
inline bool solve() {
read(n), read(m);
register int u, v;
while (m--) read(u), read(v), addEdge(u, v), addEdge(v, u), deg[u]++, deg[v]++;
for (register int u = 1; u <= n; u++) if (deg[u] & 1) return false;
for (register int u = 1; u <= n; u++) {
if (head[u]) {
dfs(u);
break;
}
}
for (register int u = 1; u <= n; u++) if (head[u]) return false;
return true;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
register int cmd;
read(cmd);
if (cmd == 1 ? UndirectedGraph::solve() : DirectedGraph::solve()) {
writeChar('Y'), writeChar('E'), writeChar('S'), writeChar('\n');
for (register int i = cnt; i; i--) write(tour[i]), writeChar(' ');
} else writeChar('N'), writeChar('O');
flush();
return 0;
}
|
