[AdditionalFile3476.zip](file://AdditionalFile3476.zip?type=additional_file)

#3476. 「ROIR 2021 Day 1」绳子

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 ROIR 2021 Day1 T4 Антенна。

有 $n$ 根绳子，第 $i$ 根绳子长 $s_i$ cm，有 $m_i$ 个节点，第 $j$ 个节点在离绳子左端点 $p_{i,j}$ cm 处。

试构造一组从左至右连接绳子的方案，设该方案的绳子顺序为 $q$，$q$ 显然会是 $1\sim n$ 的一个排列，且满足如下要求：将第 $q_i$ 根绳子的右端点与第 $q_{i+1}$ 根绳子的左端点相接后 $(1\le i<n)$，相邻的节点间的距离相等。

显然有可能没有方案，这个时候请输出 No。

输入格式

第一行为一个整数 $n$。

接下来共 $2\times n$ 行：

• 第 $2\times i(1\le i\le n)$ 行为两个整数 $m_i$ 与 $s_i$。
• 第 $2\times i+1(1\le i\le n)$ 行为 $m_i$ 个整数 $p_{i,j}$。

输出格式

若可以构造一组方案，输出 Yes，接下来再输出一行 $n$ 个整数 $q_i$。

若无解，输出 No。

样例 1

输入

3
1 7
3
1 8
6
2 8
1 6

输出

Yes
2 1 3

样例 2

输入

1
1 7
5

输出

Yes
1

样例 3

输入

1
3 10
2 5 9

输出

No

样例 4

输入

3
1 5
3
1 3
3
1 6
3

输出

No

样例 5

输入

4
1 5
0
1 0
0
1 3
3
1 0
0

输出

Yes
3 2 4 1

数据范围与提示

对于所有子任务，均有 $1\le n\le 10^5$，$1\le m_i\le 10^5$，$0\le s_i\le 10^9$，$0\le p_{i,1}<p_{i,2}<\cdots<p_{i,m_i}\le s_i$，$\sum m_i\le 10^5$。