You all know that the Library of Bookland is the largest library in the world. There are dozens of thousands of books in the library.

Some long and uninteresting story was removed...

The alphabet of Bookland is so large that its letters are denoted by positive integers. Each letter can be small or large, the large version of a letter x is denoted by x'. BSCII encoding, which is used everywhere in Bookland, is made in that way so that large letters are presented in the order of the numbers they are denoted by, and small letters are presented in the order of the numbers they are denoted by, but all large letters are before all small letters. For example, the following conditions hold: 2 < 3, 2' < 3', 3' < 2.

A word x_1, x_2, ..., x_{a} is not lexicographically greater than y_1, y_2, ..., y_{b} if one of the two following conditions holds:   a ≤ b and x_1 = y_1, ..., x_{a} = y_{a}, i.e. the first word is the prefix of the second word;  there is a position 1 ≤ j ≤ min(a, b), such that x_1 = y_1, ..., x_{j} - 1 = y_{j} - 1 and x_{j} < y_{j}, i.e. at the first position where the words differ the first word has a smaller letter than the second word has.  

For example, the word "3' 7 5" is before the word "2 4' 6" in lexicographical order. It is said that sequence of words is in lexicographical order if each word is not lexicographically greater than the next word in the sequence.

Denis has a sequence of words consisting of small letters only. He wants to change some letters to large (let's call this process a capitalization) in such a way that the sequence of words is in lexicographical order. However, he soon realized that for some reason he can't change a single letter in a single word. He only can choose a letter and change all of its occurrences in all words to large letters. He can perform this operation any number of times with arbitrary letters of Bookland's alphabet.

Help Denis to choose which letters he needs to capitalize (make large) in order to make the sequence of words lexicographically ordered, or determine that it is impossible.

Note that some words can be equal.


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of words and the number of letters in Bookland's alphabet, respectively. The letters of Bookland's alphabet are denoted by integers from 1 to m.

Each of the next n lines contains a description of one word in format l_{i}, s_{i}, 1, s_{i}, 2, ..., s_{i}, l_{i} (1 ≤ l_{i} ≤ 100 000, 1 ≤ s_{i}, j ≤ m), where l_{i} is the length of the word, and s_{i}, j is the sequence of letters in the word. The words are given in the order Denis has them in the sequence.

It is guaranteed that the total length of all words is not greater than 100 000.


-----Output-----

In the first line print "Yes" (without quotes), if it is possible to capitalize some set of letters in such a way that the sequence of words becomes lexicographically ordered. Otherwise, print "No" (without quotes).

If the required is possible, in the second line print k — the number of letters Denis has to capitalize (make large), and in the third line print k distinct integers — these letters. Note that you don't need to minimize the value k.

You can print the letters in any order. If there are multiple answers, print any of them.


-----Examples-----
Input
4 3
1 2
1 1
3 1 3 2
2 1 1

Output
Yes
2
2 3 
Input
6 5
2 1 2
2 1 2
3 1 2 3
2 1 5
2 4 4
2 4 4

Output
Yes
0

Input
4 3
4 3 2 2 1
3 1 1 3
3 2 3 3
2 3 1

Output
No



-----Note-----

In the first example after Denis makes letters 2 and 3 large, the sequence looks like the following:  2'  1  1 3' 2'  1 1 

The condition 2' < 1 holds, so the first word is not lexicographically larger than the second word. The second word is the prefix of the third word, so the are in lexicographical order. As the first letters of the third and the fourth words are the same, and 3' < 1, then the third word is not lexicographically larger than the fourth word.

In the second example the words are in lexicographical order from the beginning, so Denis can do nothing.

In the third example there is no set of letters such that if Denis capitalizes them, the sequence becomes lexicographically ordered.

Difficulty: HARD
Tags: Strong connectivity

Graph algorithms

Graph traversal

Implementation

Starter code:

Solutions:
from collections import defaultdict, deque

def main():
	(n, m) = map(int, input().split())
	cap = [None] * (m + 1)
	same_cap = defaultdict(list)
	q = deque()

	def apply_cap(a, c):
		if cap[a] is not None:
			return cap[a] == c
		q.append((a, c))
		while q:
			b = q.pop()
			if b[1] == c:
				if cap[b[0]] is None:
					cap[b[0]] = c
					q.extend(same_cap[b[0]])
					same_cap[b[0]] = []
				elif cap[b[0]] != c:
					return False
		return True

	def same(a, b):
		same_cap[b].append((a, True))
		same_cap[a].append((b, False))
		if cap[a] == False:
			return apply_cap(b, False)
		if cap[b] == True:
			return apply_cap(a, True)
		return True

	def process(p, c):
		lp = p[0]
		lc = c[0]
		for i in range(1, min(lp, lc) + 1):
			if p[i] > c[i]:
				return apply_cap(p[i], True) and apply_cap(c[i], False)
			if p[i] < c[i]:
				return same(p[i], c[i])
		return lp <= lc
	p = list(map(int, input().split()))
	for i in range(n - 1):
		c = list(map(int, input().split()))
		if not process(p, c):
			print('No')
			break
		p = c
	else:
		print('Yes')
		res = []
		for (i, b) in enumerate(cap):
			if b:
				res.append(i)
		print(len(res))
		print(' '.join(map(str, res)))
main()


import math
import collections
import bisect
import heapq
import time
import random
import itertools
(M, N) = map(int, input().split())
words = []
for i in range(M):
	words.append([int(x) for x in input().split()][1:])
C = set()
E = collections.defaultdict(list)
for i in range(M - 1):
	w1 = words[i]
	w2 = words[i + 1]
	if len(w1) > len(w2) and w1[:len(w2)] == w2:
		print('No')
		exit(0)
	for j in range(min(len(w1), len(w2))):
		if w1[j] < w2[j]:
			E[w2[j]].append(w1[j])
			break
		elif w1[j] > w2[j]:
			C.add(w1[j])
			break
A = {u for u in C}
while A:
	B = set(itertools.chain.from_iterable([E[u] for u in A]))
	A = B - C
	C |= B
for i in range(M - 1):
	w1 = words[i]
	w2 = words[i + 1]
	for j in range(min(len(w1), len(w2))):
		(a, b) = (w1[j], w2[j])
		d = [a in C, b in C]
		if a < b:
			if d == [False, True]:
				print('No')
				exit(0)
			break
		elif a > b:
			if d != [True, False]:
				print('No')
				exit(0)
			break
print('Yes')
print(len(C))
if C:
	print(' '.join(map(str, sorted(C))))


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
c = [0] * (m + 1)
ans = []
f = 0
graph = defaultdict(list)
for i in range(n - 1):
	for j in range(1, int(l[i][0]) + 1):
		if j == int(l[i + 1][0]) and int(l[i + 1][0]) < int(l[i][0]):
			if c[l[i + 1][j]] > c[l[i][j]]:
				if c[l[i][j]] == 0:
					c[l[i][j]] = 1
					break
				else:
					f = 1
					break
			if l[i][j] >= l[i + 1][j] and c[l[i][j]] <= c[l[i + 1][j]]:
				if c[l[i][j]] == 0:
					c[l[i][j]] = 1
					break
				else:
					f = 1
					break
			else:
				graph[l[i + 1][j]].append(l[i][j])
				break
		elif c[l[i + 1][j]] > c[l[i][j]]:
			if c[l[i][j]] == 0:
				c[l[i][j]] = 1
				break
			else:
				f = 1
				break
		elif l[i][j] > l[i + 1][j] and c[l[i][j]] <= c[l[i + 1][j]]:
			if c[l[i][j]] == 0:
				c[l[i][j]] = 1
				break
			else:
				f = 1
				break
		elif l[i][j] < l[i + 1][j] or c[l[i][j]] > c[l[i + 1][j]]:
			graph[l[i + 1][j]].append(l[i][j])
			break
	if f == 1:
		break
if f == 1:
	print('No')
	sys.exit(0)
f = 0
visited = [False] * (m + 1)

def dfs(v, t):
	stack = []
	stack.append((v, t))
	while len(stack) > 0:
		(v, t) = stack.pop()
		c[v] = max(t, c[v])
		visited[v] = True
		for i in graph[v]:
			c[i] = max(c[i], c[v])
			if visited[i] == False:
				stack.append((i, c[v]))
for i in range(1, m + 1):
	if visited[i] == False and c[i] == 1:
		dfs(i, c[i])
for i in range(1, m + 1):
	if c[i] == 1:
		ans.append(i)
for i in range(n - 1):
	for j in range(1, int(l[i][0]) + 1):
		if j == int(l[i + 1][0]) and int(l[i + 1][0]) < int(l[i][0]):
			if c[l[i + 1][j]] > c[l[i][j]]:
				f = 1
				break
			if l[i][j] >= l[i + 1][j] and c[l[i][j]] <= c[l[i + 1][j]]:
				f = 1
				break
			else:
				break
		if c[l[i + 1][j]] > c[l[i][j]]:
			f = 1
			break
		elif l[i][j] > l[i + 1][j] and c[l[i][j]] <= c[l[i + 1][j]]:
			f = 1
			break
		elif l[i][j] < l[i + 1][j] or c[l[i][j]] > c[l[i + 1][j]]:
			break
if f == 1:
	print('No')
else:
	print('Yes')
	print(len(ans))
	print(*ans)