import sys class InputError(Exception): pass class StrictIn: def __init__(self, s: bytes, i: int = 0, line: int = 1, col: int = 1): self.s = s self.i = i self.line = line self.col = col @staticmethod def from_stdin_ascii() -> "StrictIn": raw = sys.stdin.buffer.read() for p, b in enumerate(raw): if b >= 0x80: raise InputError(f"non-ASCII byte at offset {p}: 0x{b:02x}") if b in (0x09, 0x0A, 0x0D): continue if 0x20 <= b <= 0x7E: continue raise InputError(f"disallowed control byte at offset {p}: 0x{b:02x}") return StrictIn(raw) def _eof(self) -> bool: return self.i >= len(self.s) def _peek(self): return None if self._eof() else self.s[self.i] def _advance(self) -> int: if self._eof(): self._err("unexpected EOF") b = self.s[self.i] self.i += 1 if b == 0x0A: self.line += 1 self.col = 1 else: self.col += 1 return b def _err(self, msg: str) -> None: raise InputError(f"{msg} (line {self.line}, col {self.col})") def _consume_newline(self) -> None: b = self._peek() if b == 0x0A: self._advance() return if b == 0x0D: self._advance() if self._peek() != 0x0A: self._err("bare CR is not allowed (use LF or CRLF)") self._advance() self.line += 1 self.col = 1 return self._err("expected EOL") def skip_spaces(self) -> None: while (not self._eof()) and (self._peek() in (0x20, 0x09)): self._advance() def skip_ws(self) -> None: while not self._eof(): b = self._peek() if b in (0x20, 0x09): self._advance() elif b in (0x0A, 0x0D): self._consume_newline() else: break def read_space(self) -> None: b = self._peek() if b not in (0x20, 0x09): self._err("expected SPACE/TAB") while (not self._eof()) and (self._peek() in (0x20, 0x09)): self._advance() def read_eoln(self) -> None: self._consume_newline() def read_eof(self) -> None: if not self._eof(): self._err("expected EOF (extra data exists)") def read_token(self) -> str: b = self._peek() if b is None: self._err(f"unexpected EOF while reading token") if b in (0x20, 0x09): self._err(f"unexpected leading SPACE/TAB while reading token") if b in (0x0A, 0x0D): self._err(f"unexpected EOL while reading token") start = self.i while not self._eof(): b = self._peek() if b in (0x20, 0x09, 0x0A, 0x0D): break self._advance() return self.s[start:self.i].decode("ascii") def read_int(self, lo=None, hi=None) -> int: t_str = self.read_token() t = t_str.encode("ascii") if t[:1] == b"-": body = t[1:] if len(body) == 0: self._err(f"int is not an integer") else: body = t if len(body) == 0 or (not all(48 <= c <= 57 for c in body)): self._err(f"int is not a base-10 integer") x = int(t_str) if lo is not None and x < lo: self._err(f"int out of range: {x} < {lo}") if hi is not None and x > hi: self._err(f"int out of range: {x} > {hi}") return x def read_string(self, min_len: int | None = None, max_len: int | None = None) -> str: s = self.read_token() if min_len is not None and len(s) < min_len: self._err(f"str too short: len={len(s)} < {min_len}") if max_len is not None and len(s) > max_len: self._err(f"str too long: len={len(s)} > {max_len}") return s ins = StrictIn.from_stdin_ascii() n = ins.read_int(2, 2 * 10**5) ins.read_space() m = ins.read_int(1, n - 1) ins.read_eoln() # cnt[i] ... Ai を含む区間の LIS の最小値 cnt = [n] * n # edge ... 最小単位の区間列挙 edge = {0, n} lrk = [] c = [0]*n for _ in range(m): l = ins.read_int(1, n) ins.read_space() r = ins.read_int(l + 1, n) ins.read_space() k = ins.read_int(1, n) ins.read_eoln() for i in range(l-1, r): c[i] += 1 assert c[i] <= 2 l -= 1 lrk.append((l, r, k)) edge.add(l) edge.add(r) for i in range(l, r): cnt[i] = min(cnt[i], k) ins.read_eof() edge = sorted(edge) edge_idx = {e: i for i, e in enumerate(edge)} # cnt を圧縮 # 最小単位の区間、その区間が取る LIS をまとめる cnt_comp = [cnt[i] for i in edge[:-1]] for i in range(len(cnt_comp)): length = edge[i + 1] - edge[i] cnt_comp[i] = min(cnt_comp[i], length) # 各区間 [l:r) について LIS が k となるように最小単位の区間に値を割り振る # i 番目の最小単位の区間の要素が i-1 番目の区間の要素より diff[i] だけ大きくなるように # LIS([edge[i - 1]:edge[i]]) + diff[i] = LIS([edge[i - 1]:edge[i + 1]]) diff = [0] * len(cnt_comp) for l, r, k in lrk: li = edge_idx[l] ri = edge_idx[r] if sum(cnt_comp[li:ri]) < k: exit(print("No")) remain = k - cnt_comp[li] for i in range(li + 1, ri): diff[i] = min(cnt_comp[i], remain) remain -= diff[i] if remain: exit(print("No")) # 構築 # 最小単位の区間内は 1234444... のように構成する # diff を参考に構成し、最後に 1~N で埋める ans = [1] * n current = 1 for i in range(len(cnt_comp)): use = 0 if i != 0: use = ans[edge[i] - 1] - cnt_comp[i] + diff[i] for j in range(edge[i], edge[i + 1]): ans[j] = min(j - edge[i] + 1, cnt_comp[i]) + use mi = min(ans) for i in range(n): ans[i] += 1 - mi print("Yes") print(*ans)