// 嘘解法WA #include #include using namespace std; using namespace atcoder; int main() { int n, m; cin >> n >> m; assert(2 <= n && n <= 100000); assert(1 <= m && m <= min(100000, n * (n - 1))); vector> same, notsame; for (int i = 0; i < m; i++) { int x, y; string e; cin >> x >> e >> y; x--; y--; if (e == "<==>") same.push_back({x, y}); else notsame.push_back({x, y}); } dsu uf(n); // 「同じ」の要望についてUnionFindの辺を張る for (auto i: same) { uf.merge(i.first, i.second); } // 「同じ」の連結成分に「違う」がある場合はだめ for (auto i: notsame) { if (uf.same(i.first, i.second)) { cout << "No\n"; return 0; } } // 連結成分を求める auto gr = uf.groups(); int ns = gr.size(); vector> lds(ns); map ld; // 頂点→leaderの番号 for (int i = 0; i < ns; i++) { lds[i] = gr[i]; for (int j: gr[i]) ld[j] = i; } // 「違う」の辺を張る vector> g(ns); for (auto i: notsame) { int ldx = ld[i.first], ldy = ld[i.second]; g[ldx].push_back(ldy); g[ldy].push_back(ldx); } // 二部グラフ判定 vector col(ns, -1); for (int u = 0; u < ns; u++) { if (col[u] != -1) { continue; } col[u] = 0; queue q; q.push(u); while (!q.empty()) { int v = q.front(); q.pop(); for (auto nv : g[v]) { if (col[nv] != -1) { if (col[nv] == col[v]) { cout << "No\n"; return 0; } continue; } col[nv] = 1 - col[v]; q.push(nv); } } } vector c0, c1; for (int i = 0; i < n; i++) { if (col[ld[i]]) c1.push_back(i + 1); else c0.push_back(i + 1); } cout << "Yes\n"; // if (c0.size() * 2 >= n) { int c0s = c0.size(); cout << c0s << '\n'; for (int i = 0; i < c0s - 1; i++) { cout << c0[i] << ' '; } cout << c0[c0s - 1] << '\n'; // } /* else { int c1s = c1.size(); cout << c1s << '\n'; for (int i = 0; i < c1s - 1; i++) { cout << c1[i] << ' '; } cout << c1[c1s - 1] << '\n'; } */ }