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; }
|