题目链接 National Property
给定n个单词，字符集为m
现在我们可以把其中某些字母变成大写的。大写字母字典序大于小写字母。
问是否存在一种方案使得给定的n个单词字典序不下降。
首先判断是否存在相邻的两个单词，后一个是前一个的前缀。（两者不相等）
如果出现这种情况则直接输出无解。
建立起点s和终点t。每次扫描相邻的两个单词，找到他们第一个不相等的字母的位置。
和s相连的字母必须改成大写，和t相连的字母必须不能改成大写。
设前面那个单词的这个位置的字母为a, 后面的为b
如果a > b那么s到a之间连边，b到t之间连边（a一定要改成大写，b一定不能改成大写，否则就不成立了）
如果a < b那么b到a连一条有向边（如果a改成大写了那b更要改成大写了，因为这个关系的存在，b的字典序一定要大于a）
无解的判定：如果从s出发能走到t那么存在一个字母他必须改成大写也必须不能改成大写，矛盾。
最后把和s相连的那些字母都改成大写即可。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) const int N = 1e5 + 10; int a[N], b[N];
int n, m;
int s, t, k, ret;
int vis[N];
vector <int> v[N];
vector <int> ans; void dfs(int x){
if (x == t){ puts("No"); exit(0);}
vis[x] = 1;
ans.push_back(x);
for (auto u : v[x]) if (!vis[u]) dfs(u);
} int main(){ scanf("%d%d", &n, &m);
s = m + 1, t = m + 2;
rep(i, 1, n){
scanf("%d", b);
rep(j, 1, b[0]) scanf("%d", b + j);
if (i == 1) rep(j, 0, b[0]) a[j] = b[j];
for (k = 1; k <= a[0] && k <= b[0] && a[k] == b[k]; ) ++k;
if (k <= a[0] && k > b[0]) return 0 * puts("No");
else if (k <= a[0] && k <= b[0]){
if (a[k] > b[k]){
v[s].push_back(a[k]);
v[b[k]].push_back(t);
}
else v[b[k]].push_back(a[k]);
}
rep(j, 0, b[0]) a[j] = b[j];
} dfs(s);
printf("Yes\n%d\n", (ret = ans.size()) - 1);
rep(i, 1, ret - 1) printf("%d ", ans[i]);
return 0 * putchar(10);
}