题目描述

给定 $m$ 个要求，每个要求给定一个集合 $S$，$S$ 内的数必须连续在一段。

构造一个 $1\sim n$ 的排列满足这些要求。

首先输出排列的方案数，对 $998244353$ 取模，然后输出任意一种方案。

特别地，如果不能构造，则方案数为 $0$，且不用输出方案。可以证明，方案数如果不是 $0$，则取模后不会等于 $0$。

输入格式

第一行两个正整数 $n,m$ 表示排列大小和条件个数。$(1\le n,m\le 5000)$

接下来 $m$ 行，第一个正整数表示集合大小，然后是集合中的数，均为正整数，属于 $[1,n]$，且互不相同。

输入量可达 100MB，请使用快速的读入方式。

输出格式

第一行一个数表示方案数对 $998244353$ 取模的值。

第二行 $n$ 个数表示构造方案。

如果方案数为 $0$，不需要输出第二行。

输入输出样例

输入 1

6 6
2 1 5
4 1 2 4 5
3 2 3 6
2 2 5
1 4
3 2 3 6

输出 1

4
4 1 5 2 3 6

样例 1 解释

四种情况为：

4 1 5 2 3 6
4 1 5 2 6 3
6 3 2 5 1 4
3 6 2 5 1 4

输入 2

3 3
2 1 2
2 1 3
2 2 3

输出 2

0

Source

jerry3128