結果

問題 No.2536 同値性と充足可能性
ユーザー mattu34
提出日時 2023-11-13 07:56:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 717 ms / 2,000 ms
コード長 27,364 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 110,184 KB
最終ジャッジ日時 2024-09-26 03:14:25
合計ジャッジ時間 8,157 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):  # 多用すると重い
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members
    def __str__(self):
        return "\n".join(f"{r}: {m}" for r, m in self.all_group_members().items())
class WeightedUnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.diff_weight = [0] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            r = self.find(self.parents[x])
            self.diff_weight[x] += self.diff_weight[self.parents[x]]
            self.parents[x] = r
            return r
    def weight(self, x):
        self.find(x)
        return self.diff_weight[x]
    def union(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
            w = -w
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.diff_weight[y] = w
    def diff(self, x, y):
        return self.weight(x) - self.weight(y)
# uf = WeightedUnionFind(N)
# uf.union(y,x,z) # Ay = Ax + z
# uf.diff(x,y) # Ay-Axを返す
# https://raw.githubusercontent.com/shakayami/ACL-for-python/master/segtree.py
class segtree:
    n = 1
    size = 1
    log = 2
    d = [0]
    op = None
    e = 10**15
    def __init__(self, V, OP, E):
        self.n = len(V)
        self.op = OP
        self.e = E
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)
    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)
    def get(self, p):
        assert 0 <= p and p < self.n
        return self.d[p + self.size]
    def prod(self, l, r):
        assert 0 <= l and l <= r and r <= self.n
        sml = self.e
        smr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                smr = self.op(self.d[r - 1], smr)
                r -= 1
            l >>= 1
            r >>= 1
        return self.op(sml, smr)
    def all_prod(self):
        return self.d[1]
    def max_right(self, l, f):
        assert 0 <= l and l <= self.n
        assert f(self.e)
        if l == self.n:
            return self.n
        l += self.size
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not (f(self.op(sm, self.d[l]))):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l:
                break
        return self.n
    def min_left(self, r, f):
        assert 0 <= r and r <= self.n
        assert f(self.e)
        if r == 0:
            return 0
        r += self.size
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not (f(self.op(self.d[r], sm))):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                break
        return 0
    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
    def __str__(self):
        return str([self.get(i) for i in range(self.n)])
    def get_list(self):
        return [self.get(i) for i in range(self.n)]  # オリジナルで追加
# RMQのとき
# def op(x, y):
#    return x if x < y else y
# seg = segtree([10**9] * N, op, 10**9)  # Vの要素とEの値は同じにする #10**9 -> INF
# seg.prod(l, r) # op(a[l],...a[r-1])を返す
# https://github.com/shakayami/ACL-for-python/blob/master/lazysegtree.py
class lazy_segtree:
    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])
    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.identity
    def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
        self.n = len(V)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        self.lz = [ID for i in range(self.size)]
        self.e = E
        self.op = OP
        self.mapping = MAPPING
        self.composition = COMPOSITION
        self.identity = ID
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)
    # Args:
    #         N (int): 配列の長さ
    #         op (Callable[[S, S], S]): 区間取得に用いる演算
    #         E: 全てのaに対して op(a, e) = a が成り立つ単位元
    #         MAPPING (Callable[[F, S], S]): dataに作用させる関数
    #         COMPOSITION (Callable[[F, F], F]): lazyに作用させる関数 f(g(x))
    #         ID: 全てのaに対して mapping(id, a) = a が成り立つ恒等写像
    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)
    def get(self, p):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]
    def prod(self, l, r):
        assert 0 <= l and l <= r and r <= self.n
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.push(l >> i)
            if ((r >> i) << i) != r:
                self.push(r >> i)
        sml, smr = self.e, self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)
    def all_prod(self):
        return self.d[1]
    def apply_point(self, p, f):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)
    def apply(self, l, r, f):
        assert 0 <= l and l <= r and r <= self.n
        if l == r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.push(l >> i)
            if ((r >> i) << i) != r:
                self.push((r - 1) >> i)
        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2
        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l:
                self.update(l >> i)
            if ((r >> i) << i) != r:
                self.update((r - 1) >> i)
    def max_right(self, l, g):
        assert 0 <= l and l <= self.n
        assert g(self.e)
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not (g(self.op(sm, self.d[l]))):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l:
                break
        return self.n
    def min_left(self, r, g):
        assert 0 <= r and r <= self.n
        assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push((r - 1) >> i)
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not (g(self.op(self.d[r], sm))):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                break
        return 0
# ACLのではない。機能は減るが、こっちのほうが早い
class LazySegTree:
    def __init__(self, v, op, e, mapping, composition, id_):
        n = len(v)
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_
        self._size = 1 << (n - 1).bit_length()
        self._d = [e] * (2 * self._size)
        self._lz = [id_] * 2 * self._size
        for i in range(n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1])
    def _gindex(self, l, r):
        l += self._size
        r += self._size
        lm = l >> (l & -l).bit_length()
        rm = r >> (r & -r).bit_length()
        while r > l:
            if l <= lm:
                yield l
            if r <= rm:
                yield r
            l >>= 1
            r >>= 1
        while l:
            yield l
            l >>= 1
    def _propagates(self, *ids):
        for i in reversed(ids):
            f = self._lz[i]
            self._lz[i] = self._id
            self._lz[2 * i] = self._composition(f, self._lz[2 * i])
            self._lz[2 * i + 1] = self._composition(f, self._lz[2 * i + 1])
            self._d[2 * i] = self._mapping(f, self._d[2 * i])
            self._d[2 * i + 1] = self._mapping(f, self._d[2 * i + 1])
    def apply(self, l, r, f):
        (*ids,) = self._gindex(l, r)
        self._propagates(*ids)
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                self._lz[l] = self._composition(f, self._lz[l])
                self._d[l] = self._mapping(f, self._d[l])
                l += 1
            if r & 1:
                self._lz[r - 1] = self._composition(f, self._lz[r - 1])
                self._d[r - 1] = self._mapping(f, self._d[r - 1])
            l >>= 1
            r >>= 1
        for i in ids:
            self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1])
    def prod(self, l, r):
        self._propagates(*self._gindex(l, r))
        resl = self._e
        resr = self._e
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                resl = self._op(resl, self._d[l])
                l += 1
            if r & 1:
                resr = self._op(self._d[r - 1], resr)
            l >>= 1
            r >>= 1
        return self._op(resl, resr)
# RMQのとき
# def op(a, b):
#     if a > b:
#         return b
#     return a
# def mapping(f, x): # 更新(dataに作用, fは上書きフラグ(f==ID: False))
#     if f == ID:
#         return x
#     return f
# def composition(f, g): # 更新(lazyに作用, fは上書きフラグ(f==ID: False), 作用順はg→f)
#     if f == ID:
#         return g
#     return f
# ini = INF
# ID = ini
# lst = lazy_segtree([ini] * len(d), op, ini, mapping, composition, ID)
# lst.apply(l, r, x)
# lst.prod(l, r)
# RAQのとき
# def mapping(f, x):
#     return f + x
# def composition(f, g):
#     return f + g
# https://github.com/shakayami/ACL-for-python/blob/master/string.py
class string:
    def sa_is(s, upper):
        n = len(s)
        if n == 0:
            return []
        if n == 1:
            return [0]
        if n == 2:
            if s[0] < s[1]:
                return [0, 1]
            else:
                return [1, 0]
        sa = [0] * n
        ls = [0] * n
        for i in range(n - 2, -1, -1):
            ls[i] = ls[i + 1] if (s[i] == s[i + 1]) else (s[i] < s[i + 1])
        sum_l = [0] * (upper + 1)
        sum_s = [0] * (upper + 1)
        for i in range(n):
            if not (ls[i]):
                sum_s[s[i]] += 1
            else:
                sum_l[s[i] + 1] += 1
        for i in range(upper + 1):
            sum_s[i] += sum_l[i]
            if i < upper:
                sum_l[i + 1] += sum_s[i]
        def induce(lms):
            for i in range(n):
                sa[i] = -1
            buf = sum_s[:]
            for d in lms:
                if d == n:
                    continue
                sa[buf[s[d]]] = d
                buf[s[d]] += 1
            buf = sum_l[:]
            sa[buf[s[n - 1]]] = n - 1
            buf[s[n - 1]] += 1
            for i in range(n):
                v = sa[i]
                if v >= 1 and not (ls[v - 1]):
                    sa[buf[s[v - 1]]] = v - 1
                    buf[s[v - 1]] += 1
            buf = sum_l[:]
            for i in range(n - 1, -1, -1):
                v = sa[i]
                if v >= 1 and ls[v - 1]:
                    buf[s[v - 1] + 1] -= 1
                    sa[buf[s[v - 1] + 1]] = v - 1
        lms_map = [-1] * (n + 1)
        m = 0
        for i in range(1, n):
            if not (ls[i - 1]) and ls[i]:
                lms_map[i] = m
                m += 1
        lms = []
        for i in range(1, n):
            if not (ls[i - 1]) and ls[i]:
                lms.append(i)
        induce(lms)
        if m:
            sorted_lms = []
            for v in sa:
                if lms_map[v] != -1:
                    sorted_lms.append(v)
            rec_s = [0] * m
            rec_upper = 0
            rec_s[lms_map[sorted_lms[0]]] = 0
            for i in range(1, m):
                l = sorted_lms[i - 1]
                r = sorted_lms[i]
                end_l = lms[lms_map[l] + 1] if (lms_map[l] + 1 < m) else n
                end_r = lms[lms_map[r] + 1] if (lms_map[r] + 1 < m) else n
                same = True
                if end_l - l != end_r - r:
                    same = False
                else:
                    while l < end_l:
                        if s[l] != s[r]:
                            break
                        l += 1
                        r += 1
                    if (l == n) or (s[l] != s[r]):
                        same = False
                if not (same):
                    rec_upper += 1
                rec_s[lms_map[sorted_lms[i]]] = rec_upper
            rec_sa = string.sa_is(rec_s, rec_upper)
            for i in range(m):
                sorted_lms[i] = lms[rec_sa[i]]
            induce(sorted_lms)
        return sa
    def suffix_array_upper(s, upper):
        assert 0 <= upper
        for d in s:
            assert 0 <= d and d <= upper
        return string.sa_is(s, upper)
    def suffix_array(s):
        n = len(s)
        if type(s) == str:
            s2 = [ord(i) for i in s]
            return string.sa_is(s2, 255)
        else:
            idx = list(range(n))
            idx.sort(key=lambda x: s[x])
            s2 = [0] * n
            now = 0
            for i in range(n):
                if i & s[idx[i - 1]] != s[idx[i]]:
                    now += 1
                s2[idx[i]] = now
            return string.sa_is(s2, now)
    def lcp_array(s, sa):
        n = len(s)
        assert n >= 1
        rnk = [0] * n
        for i in range(n):
            rnk[sa[i]] = i
        lcp = [0] * (n - 1)
        h = 0
        for i in range(n):
            if h > 0:
                h -= 1
            if rnk[i] == 0:
                continue
            j = sa[rnk[i] - 1]
            while j + h < n and i + h < n:
                if s[j + h] != s[i + h]:
                    break
                h += 1
            lcp[rnk[i] - 1] = h
        return lcp
    def z_algorithm(s):
        n = len(s)
        if n == 0:
            return []
        z = [0] * n
        i = 1
        j = 0
        while i < n:
            z[i] = 0 if (j + z[j] <= i) else min(j + z[j] - i, z[i - j])
            while (i + z[i] < n) and (s[z[i]] == s[i + z[i]]):
                z[i] += 1
            if j + z[j] < i + z[i]:
                j = i
            i += 1
        z[0] = n
        return z
# suffix_arrayの作り方
# S = "abcababaabc"
# sa = string.suffix_array(S)
# lcp = string.lcp_array(S, sa)
class BIT:
    def __init__(self, n):
        self.n = len(n) if isinstance(n, list) else n
        self.size = 1 << (self.n - 1).bit_length()
        if isinstance(n, list):  # nは1-indexedなリスト
            a = [0]
            for p in n:
                a.append(p + a[-1])
            a += [a[-1]] * (self.size - self.n)
            self.d = [a[p] - a[p - (p & -p)] for p in range(self.size + 1)]
        else:  # nは大きさ
            self.d = [0] * (self.size + 1)
    def __repr__(self):
        p = self.size
        res = []
        while p > 0:
            res2 = []
            for r in range(p, self.size + 1, p * 2):
                l = r - (r & -r) + 1
                res2.append(f"[{l}, {r}]:{self.d[r]}")
            res.append(" ".join(res2))
            p >>= 1
        res.append(f"{[self.sum(p + 1) - self.sum(p) for p in range(self.size)]}")
        return "\n".join(res)
    def add(self, p, x):  # O(log(n)), 点pにxを加算
        assert p > 0
        while p <= self.size:
            self.d[p] += x
            p += p & -p
    def get(self, p, default=None):  # O(log(n))
        assert p > 0
        return (
            self.sum(p) - self.sum(p - 1)
            if 1 <= p <= self.n or default is None
            else default
        )
    def sum(self, p):  # O(log(n)), 閉区間[1, p]の累積和
        assert p >= 0
        res = 0
        while p > 0:
            res += self.d[p]
            p -= p & -p
        return res
    def lower_bound(self, x):  # O(log(n)), x <= 閉区間[1, p]の累積和 となる最小のp
        if x <= 0:
            return 0
        p, r = 0, self.size
        while r > 0:
            if p + r <= self.n and self.d[p + r] < x:
                x -= self.d[p + r]
                p += r
            r >>= 1
        return p + 1
class MultiSet:
    # n: サイズ、compress: 座圧対象list-likeを指定(nは無効)
    # multi: マルチセットか通常のOrderedSetか
    def __init__(self, n=0, *, compress=[], multi=True):
        self.multi = multi
        self.inv_compress = (
            sorted(set(compress)) if len(compress) > 0 else [i for i in range(n)]
        )
        self.compress = {k: v for v, k in enumerate(self.inv_compress)}
        self.counter_all = 0
        self.counter = [0] * len(self.inv_compress)
        self.bit = BIT(len(self.inv_compress))
    def add(self, x, n=1):  # O(log n)
        if not self.multi and n != 1:
            raise KeyError(n)
        x = self.compress[x]
        count = self.counter[x]
        if count == 0 or self.multi:  # multiなら複数カウントできる
            self.bit.add(x + 1, n)
            self.counter_all += n
            self.counter[x] += n
    def remove(self, x, n=1):  # O(log n)
        if not self.multi and n != 1:
            raise KeyError(n)
        x = self.compress[x]
        count = self.bit.get(x + 1)
        if count < n:
            raise KeyError(x)
        self.bit.add(x + 1, -n)
        self.counter_all -= n
        self.counter[x] -= n
    def __repr__(self):
        return f'MultiSet {{{(", ".join(map(str, list(self))))}}}'
    def __len__(self):  # oprator len: O(1)
        return self.counter_all
    def count(self, x):  # O(1)
        return self.counter[self.compress[x]] if x in self.compress else 0
    def __getitem__(self, i):  # operator []: O(log n)
        if i < 0:
            i += len(self)
        x = self.bit.lower_bound(i + 1)
        if x > self.bit.n:
            raise IndexError("list index out of range")
        return self.inv_compress[x - 1]
    def __contains__(self, x):  # operator in: O(1)
        return self.count(x) > 0
    def bisect_left(self, x):  # O(log n)
        return self.bit.sum(bisect.bisect_left(self.inv_compress, x))
    def bisect_right(self, x):  # O(log n)
        return self.bit.sum(bisect.bisect_right(self.inv_compress, x))
# 宣言方法
# MultiSet(compress=X,multi=False)
# MultiSet(N+1,multi=True)
# リストを渡すと座標圧縮して返してくれる
def compress(arr):
    (*XS,) = set(arr)
    XS.sort()
    return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)}
def ctov(c):
    return ord(c) - ord("a")
def CTOV(c):
    return ord(c) - ord("A")
# 約数列挙
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
# 素因数分解(辞書)
def prime_factorize(n):
    V = defaultdict(int)
    i = 2
    while i**2 <= n:
        while n % i == 0:
            V[i] += 1
            n //= i
        i += 1
    if n != 1:
        V[n] += 1
    return V
def convert_90(matrix):
    # 入力行列の行数と列数を取得
    rows = len(matrix)
    cols = len(matrix[0])
    # 90度回転後の行列を初期化
    rotated_matrix = [[0] * rows for _ in range(cols)]
    # 元の行列を90度回転させて新しい行列に格納
    for i in range(rows):
        for j in range(cols):
            rotated_matrix[j][rows - 1 - i] = matrix[i][j]
    return rotated_matrix
def cropping(MAP, mark):
    M_y, M_x = 0, 0
    m_y, m_x = INF, INF
    H, W = len(MAP), len(MAP[0])
    for i in range(H):
        for j in range(W):
            if MAP[i][j] == mark:
                M_y = max(i, M_y)
                M_x = max(M_x, j)
                m_y = min(i, m_y)
                m_x = min(m_x, j)
    new = [[0] * (M_x - m_x + 1) for _ in range(M_y - m_y + 1)]
    for i in range(m_y, M_y + 1):
        for j in range(m_x, M_x + 1):
            new[i - m_y][j - m_x] = MAP[i][j]
    return new
def cos(theta):
    theta_rad = math.radians(theta)
    cos_value = math.cos(theta_rad)
    return cos_value
    return math.acos(val)
def sin(theta):
    theta_rad = math.radians(theta)
    sin_value = math.sin(theta_rad)
    return sin_value
def acos(value):
    radians = math.acos(value)
    degrees = math.degrees(radians)
    return degrees
# ダブリング dp[i][j]:=jから2**i回遷移したときの到達点
# https://atcoder.jp/contests/abc167/submissions/40815296
# N,K=map(int,input().split())
# A=list(map(int,input().split()))
# dp=[[-1]*N for _ in range(60)]
# for j in range(N):
#     dp[0][j]=A[j]-1
# for i in range(1,60):
#     for j in range(N):
#         dp[i][j]=dp[i-1][dp[i-1][j]]
# i=0
# now=0
# while(K>0):
#     if (K&1)==1:
#         now=dp[i][now]
#     i+=1
#     K>>=1
# print(now+1)
# 牛ゲー
# xj-xi<=bkの条件の下で、xt-xsを最大化する問題
# i→jへ、重みbkの有効辺をはったとき、sからtまでの最短距離がxt-xsの最大値と一致する。
# 到達できない場合は、xt-xsは無限大
from collections import *
import sys
import heapq
import bisect
import itertools
dxdy1 = ((0, 1), (0, -1), (1, 0), (-1, 0))
dxdy2 = ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1))
dxdy3 = ((0, 1), (1, 0))
dxdy4 = ((1, 1), (1, -1), (-1, 1), (-1, -1))
INF = float("inf")
MOD = 998244353
mod = 998244353
MOD2 = 10**9 + 7
mod2 = 10**9 + 7
# memo : len([a,b,...,z])==26
input = lambda: sys.stdin.readline().rstrip()
mi = lambda: map(int, input().split())
li = lambda: list(mi())
N, M = mi()
adj = [[] for _ in range(2 * N)]
uf = UnionFind(2 * N)
for _ in range(M):
    x, E, y = map(str, input().split())
    x, y = int(x), int(y)
    x -= 1
    y -= 1
    if E == "<==>":
        uf.union(x, y)
        uf.union(x + N, y + N)
        adj[x].append(y)
        adj[y].append(x)
        adj[x + N].append(y + N)
        adj[y + N].append(x + N)
    else:
        uf.union(x, y + N)
        uf.union(x + N, y)
        adj[x].append(y + N)
        adj[y + N].append(x)
        adj[x + N].append(y)
        adj[y].append(x + N)
for i in range(N):
    if uf.same(i, i + N):
        print("No")
        exit()
visited = [0] * N
one = []
zero = []
for i in range(N):
    if visited[i] == 1:
        continue
    one.append(i + 1)
    visited[i] = 1
    q = deque()
    q.append(i)
    while q:
        node = q.pop()
        for nxt in adj[node]:
            if nxt >= N:
                if visited[nxt - N] == 1:
                    continue
                visited[nxt - N] = 1
                q.append(nxt)
                zero.append(nxt - N + 1)
            else:
                if visited[nxt] == 1:
                    continue
                visited[nxt] = 1
                q.append(nxt)
                one.append(nxt + 1)
# print(one, zero)
print("Yes")
if len(one) < (N + 1) // 2:
    zero.sort()
    print(len(zero))
    print(*zero)
else:
    one.sort()
    print(len(one))
    print(*one)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0