結果
| 問題 | No.2536 同値性と充足可能性 |
| ユーザー |
 mattu34
|
| 提出日時 | 2023-11-13 07:52:41 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 27,341 bytes |
| コンパイル時間 | 183 ms |
| コンパイル使用メモリ | 82,560 KB |
| 実行使用メモリ | 109,504 KB |
| 最終ジャッジ日時 | 2024-09-26 03:13:49 |
| 合計ジャッジ時間 | 8,352 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 61 ms
61,056 KB |
| testcase_01 | AC | 60 ms
60,416 KB |
| testcase_02 | AC | 60 ms
60,416 KB |
| testcase_03 | AC | 62 ms
60,800 KB |
| testcase_04 | AC | 61 ms
61,056 KB |
| testcase_05 | AC | 61 ms
60,672 KB |
| testcase_06 | AC | 61 ms
60,672 KB |
| testcase_07 | AC | 61 ms
60,800 KB |
| testcase_08 | AC | 61 ms
60,416 KB |
| testcase_09 | AC | 61 ms
60,928 KB |
| testcase_10 | AC | 61 ms
60,672 KB |
| testcase_11 | AC | 60 ms
60,544 KB |
| testcase_12 | WA | - |
| testcase_13 | AC | 60 ms
60,672 KB |
| testcase_14 | AC | 61 ms
60,544 KB |
| testcase_15 | AC | 61 ms
60,928 KB |
| testcase_16 | AC | 62 ms
60,672 KB |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | AC | 62 ms
61,184 KB |
| testcase_20 | AC | 104 ms
77,184 KB |
| testcase_21 | AC | 130 ms
77,696 KB |
| testcase_22 | AC | 114 ms
77,568 KB |
| testcase_23 | AC | 332 ms
87,316 KB |
| testcase_24 | AC | 298 ms
85,712 KB |
| testcase_25 | AC | 686 ms
109,416 KB |
| testcase_26 | AC | 691 ms
109,504 KB |
| testcase_27 | AC | 620 ms
109,280 KB |
| testcase_28 | AC | 620 ms
109,304 KB |
| testcase_29 | AC | 593 ms
106,760 KB |
| testcase_30 | AC | 489 ms
107,916 KB |
ソースコード
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 - M)
else:
if visited[nxt] == 1:
continue
visited[nxt] = 1
q.append(nxt)
one.append(nxt + 1)
print("Yes")
if len(one) < (N + 1) // 2:
zero.sort()
print(len(zero))
print(*zero)
else:
one.sort()
print(len(one))
print(*one)