import std; struct pair { int u; int v; } void main () { int N, M; readln.read(N, M); pair[] P1; pair[] P2; foreach (i; 0..M) { int u, v; string type; readln.read(u, type, v); u--, v--; if (type == "<==>") { P1 ~= pair(u, v); } if (type == "<=/=>") { P2 ~= pair(u, v); } } solve(N, M, P1, P2); } void solve (int N, int M, pair[] P1, pair[] P2) { /* アッ!どっちもとらなくてよい場合があるの忘れてた! */ /* すみません。。。作り直します。 */ /* まず、タイプ2の命題で張られる辺をたどっていき、頂点を交互に彩色する。 ある命題が存在して、違う色を結んでいたら即死亡 そうでなければ、あとは取る数が足りるかどうかの勝負 どちらかの色を採用すると決め打ちしてタイプ1命題を探索する。 タイプ1命題の成すグラフを考えると、連結成分を全部取らないor全部取るしかない。 取れるやつを全部取る。 */ int[][] graph = new int[][](N, 0); foreach (p; P2) { graph[p.u] ~= p.v; graph[p.v] ~= p.u; } bool isOk = true; bool[] visited = new bool[](N); int[] color = new int[](N); color[] = -1; // -1は未彩色 void dfs (int pos, int depth) { visited[pos] = true; /* 矛盾のチェック */ if ( (depth % 2 == 0 && color[pos] == 1) || (depth % 2 == 1 && color[pos] == 0) ) { isOk = false; } if (depth % 2 == 0) color[pos] = 0; if (depth % 2 == 1) color[pos] = 1; foreach (to; graph[pos]) { if (!visited[to]) dfs(to, depth+1); } } foreach (p; P2) { if (color[p.u] == -1 && color[p.v] == -1) dfs(p.u, 0); } bool[] used = new bool[](N); int[] took; /* 命題1の成す連結成分をUFで管理 */ auto UF = UnionFind!(int)(N); foreach (p; P1) { UF.unite(p.u, p.v); } /* 輪から外れてる奴ら */ int[] unemployed; foreach (g; UF.enumerateGroups) foreach (v; g) if (color[v] == -1) unemployed ~= v; bool check (int c) { if (!isOk) return false; took.length = 0; used[] = false; foreach (i; 0..N) if (color[i] == c) used[i] = true; /* 命題1をとるぜよ */ foreach (g; UF.enumerateGroups) { bool take = true; foreach (v; g) { if (color[v] == c || color[v] == -1) continue; take = false; break; } if (take) foreach (v; g) used[v] = true; } /* なんも関係ないやつらは勝手にとれるよな? */ foreach (u; unemployed) used[u] = true; /* 命題1のチェック */ foreach (p; P1) { if (used[p.u] && used[p.v]) continue; if (!used[p.u] && !used[p.v]) continue; return false; } foreach (i; 0..N) if (used[i]) took ~= i+1; /* 数のチェック */ if (took.length < (N+2-1)/2) return false; writeln("Yes"); writeln(took.length); took.sort; foreach (i, t; took) write(t, i == took.length-1 ? '\n' : ' '); return true; } foreach (c; [0, 1]) if (check(c)) return; writeln("No"); } void read(T...)(string S, ref T args) { auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } } /** * TODO * - クラスの各関数の仕様をまとめる * - コンストラクタ関数の仕様をまとめる * - assertで落としたときにstderrにメッセージを表示 * - 関数名を変えるかもしれん(uniteとareInSameGroupとの整合性が取れてなさすぎ) * * VERYFYIED * - uniteとareInSameGroup : yosupo judge (https://judge.yosupo.jp/problem/unionfind) * * UNVERYFYIED * - countGroups * - GroupSize * - enumerateGroups */ /* ------------------------------ */ /* class definition */ /* ------------------------------ */ class UnionFind_Dictionary (T) { private: T[T] parent; int[T] size; T findRoot (T x) { if (x !in parent) { addElement(x); return x; } if (parent[x] == x) return x; return parent[x] = findRoot(parent[x]); } bool areInSameGroup (T x, T y) { return findRoot(x) == findRoot(y); } void unite (T x, T y) { addElement(x), addElement(y); T larger, smaller; if (GroupSize(x) <= GroupSize(y)) { larger = findRoot(y); smaller = findRoot(x); } else { larger = findRoot(x); smaller = findRoot(y); } if (larger == smaller) return; parent[smaller] = larger; size[larger] += size[smaller]; } int countGroups () { int res = 0; foreach (key, val; parent) { if (key == val) res++; } return res; } bool addElement (T x) { if (x in parent) return false; parent[x] = x; size[x] = 1; return true; } int GroupSize (T x) { addElement(x); return size[findRoot(x)]; } T[][] enumerateGroups (T x) { T[][T] mp; foreach (key, val; parent) { mp[val] ~= key; } T[][] res = new T[][](mp.length, 0); int idx = 0; foreach (val; mp) { res[idx] = val; idx++; } return res; } } class UnionFind_Array { private: int N; int[] parent; int[] size; this (int N) in { assert(0 <= N, "N must be positive integer."); } do { this.N = N; parent = new int[](N); size = new int[](N); foreach (i; 0..N) { parent[i] = i; size[i] = 1; } } int findRoot (int x) in { assert(0 <= x && x < N); } do { if (parent[x] == x) return x; return parent[x] = findRoot(parent[x]); } bool areInSameGroup (int x, int y) in { assert(0 <= x && x < N); assert(0 <= y && y < N); } do { return findRoot(x) == findRoot(y); } void unite (int x, int y) in { assert(0 <= x && x < N); assert(0 <= y && y < N); } do { int larger, smaller; if (GroupSize(x) <= GroupSize(y)) { larger = findRoot(y); smaller = findRoot(x); } else { larger = findRoot(x); smaller = findRoot(y); } if (larger == smaller) return; parent[smaller] = larger; size[larger] += size[smaller]; } int countGroups () { int res = 0; foreach (x, par; parent) { if (x == par) res++; } return res; } int GroupSize (int x) in { assert(0 <= x && x < N); } do { return size[findRoot(x)]; } int[][] enumerateGroups () { int[][] mp = new int[][](N, 0); int resSize = 0; foreach (v, par; parent) { if (mp[par].length == 0) resSize++; mp[par] ~= cast(int) v; } int[][] res = new int[][](resSize); int idx = 0; foreach (m; mp) { if (m.length == 0) continue; res[idx] = m; idx++; } return res; } } /* ------------------------------ */ /* Constructors */ /* ------------------------------ */ /* Dictionary UF */ auto UnionFind (T) () { return new UnionFind_Dictionary!(T)(); } import std.range.primitives : isInputRange; auto UnionFind (T, E) (E range) if (isInputRange!(E) || is(T == S[], S) || is(T == S[n], S, size_t n)) { auto res = new UnionFind_Dictionary!(T)(); foreach (elem; range) { res.addElement(elem); } return res; } /* Array UF */ auto UnionFind (T) (int N) if (is(T == int)) { return new UnionFind_Array(N); }