参考：出题人 Itst 的题解。
确实是神仙，不好想。
Description
有一个帖子，总共有 $n$ 个人在帖子里发过消息。这个帖子里有 $m$ 条消息，每条消息包含三个字符串 $s1,s2,s3$，$s1$ 代表发出者的名字。消息分三类：
- 楼上型消息：如果 $s3$ 是
loushang，且 $s2$ 是在帖子里发过贴的人的名字，那么称该消息为楼上型消息，该消息被满足当且仅当上一条消息的发出者为 $s2$； - 楼下型消息：如果 $s3$ 是
louxia，且 $s2$ 是在帖子里发过贴的人的名字，那么称该消息为楼下型消息，该消息被满足当且仅当下一条消息的发出者为 $s2$； - 学术消息：不满足以上条件即为学术消息。这类消息无法被满足。
你需要对这 $m$ 条消息进行重新排列使得被满足的消息数量最大，输出这个最大值以及排列。
保证每个人至少发过一条学术消息。
多组数据，数据组数 $T\leq100$，$n\leq m\leq77777$，$\sum m\leq2.5\times10^5$。
Solution
让我们忽略魔怔的题面，来分析这个问题吧。
首先题目中的楼上型消息和楼下型消息很容易想到可以用边的方式去刻画，我们有了一个初步的方向：加边加边加边，跑某某某算法。
特殊性质 BC
因为每个消息都能被满足，且没有互相满足的消息，最后的帖子一定是由若干块下面这种形式组成：
A B loushang
B C loushang
C C C
D C louxia
A D louxia
即若干个楼上消息，一个学术消息，若干个楼下消息。
一个简单想法是：把满足要求的消息按照楼上到楼下的方向连边，把这种形式抽象为一条链，然后搞欧拉回路之类的覆盖所有边的算法。
比如 A B loushang，就从 $A$ 向 $B$ 连边，A B louxia，就从 $B$ 向 $A$ 连边。
乍一看挺对，但直接连边是不能体现出经过学术消息走到楼下消息这一不可逆的过程，对于这种不可逆的边我们可以用分层图来描述：
建立二层图 $G_1,G_2$，对于楼上型消息，我们在 $G_1$ 中连边；对于楼下型消息，我们在 $G_2$ 中连边；对于学术消息，我们把发出者从 $G_1$ 连向 $G_2$，这样一个块就是从 $G_1$ 出发经过若干条边然后走一个学术边到达 $G_2$ 再走若干条边结束。
因为所有消息都可以被满足，我们建一个辅助点然后平衡一下度数，跑欧拉回路就好了。
具体而言就是 $G_1$ 要是入度不够就从辅助点向它连边，$G_2$ 相反。
特殊性质 C
现在有消息不能被满足了，也就是说 $G_1$ 中有点入度大于出度，这些入度减出度条边无法满足要求，$G_2$ 中就是反过来。
首先我们如果把多的边全都扔掉肯定是可以构造出一组方案的，但是并不一定是最优，因为扔掉的边可以变为学术消息再次利用。变成学术消息后 $G_1$ 中对应点入度会减 $1$，$G_2$ 中对应点入度会加 $1$，这样我们扔掉了一条边，而可以满足两个需要的边。
我们要让扔掉一些边之后能尽可能多匹配不能被满足的边。
问题转化为：每个点有一个需求，而假如舍弃一条边，可以满足 $G_1,G_2$ 中各一个点的需求减去 $1$，要最大化满足的需求。
然后这个问题很明显可以用最大流求解，源点向 $G_1$ 中的点连流量为该点不能满足的边的数量，$G_2$ 中的点向汇点连该点不能满足的边的数量。对于一条边 A B loushang，我们从 $G_1$ 的 $B$ 连向 $G_2$ 的 $A$，流量为 $1$，表示断掉这条边，这两个点的需求都减少 $1$；楼下消息同理。
接下来我们把被舍弃的边看作学术消息，做特殊性质 BC 就可以了。
无特殊性质
现在没有了特殊性质 C，不同就是一条链的中间点除了是学术消息，还可以是下面这种形式：
A B loushang
B A louxia
因为这部分没多少分我们可以直接猜测只需要把边简单地缩起来就可以搞定
调整法就可以证明，把这两条消息看成一条从 $A$ 到 $B$ 的学术消息边一定是不劣的。
简单证明一下就是如果拆开，那么把 A B loushang 的上面匹配的楼上消息以及 B A louxia 下面匹配的楼下消息都搬出来，再合到一起去，肯定是不劣的。
然后我们就可以快乐地把这两条边看成一条学术边然后做特殊性质 C 了，好耶！
实现的时候发现一个小问题：缩起来的边在跑欧拉路的时候记录方案略难受，我的方法是对于每组边，再建一个虚点，$A$ 向虚点连边，虚点向 $B$ 连边。
时间复杂度为预处理 $O(m\log m)$，最大流 $O(dinic)$，欧拉路 $O(n+m)$，加起来反正能过。
我感觉这个二分图，流量不大，dinic应该是很快的。
Code
不是非常好写，码量略大。
namespace solve
{
const int maxn = 3e5 + 10;
const int inf = 1e9;
const string louxia = "louxia";
const string loushang = "loushang";
typedef pair<int, int> pii;
int n, m;
unordered_map<string, int> mp;
vector<int> a[maxn];
int ans[maxn];
struct message
{
int x, y, type;
// 1 楼上 2 楼下
} all[maxn];
int cnt = 0;
namespace flow
{
struct edge
{
int x, y, cap, flow;
int now_flow() { return cap - flow; }
};
vector<edge> edges;
vector<int> e[maxn];
inline int add(int x, int y, int cap)
{
cnt++;
edges.push_back({x, y, cap, 0});
edges.push_back({y, x, 0, 0});
int m = edges.size();
e[x].push_back(m - 2), e[y].push_back(m - 1);
return m - 2;
}
int cur[maxn], vis[maxn], s, t, dis[maxn];
bool bfs()
{
fill(vis, vis + t + 1, 0);
dis[s] = 0, vis[s] = 1;
queue<int> q;
q.push(s);
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i : e[x])
{
auto &k = edges[i];
if (!vis[k.y] && k.cap - k.flow > 0)
{
dis[k.y] = dis[x] + 1;
vis[k.y] = 1, q.push(k.y);
}
}
}
return vis[t];
}
int dfs(int x, int lim)
{
if (x == t || lim == 0)
return lim;
int res = 0, f;
for (int &i = cur[x]; i < (int)e[x].size(); i++)
{
auto &k = edges[e[x][i]];
if (dis[x] + 1 != dis[k.y] || (f = dfs(k.y, min(lim, k.cap - k.flow))) == 0)
continue;
res += f, lim -= f, k.flow += f, edges[e[x][i] ^ 1].flow -= f;
if (lim == 0)
break;
}
return res;
}
int dinic(int s_, int t_)
{
s = s_, t = t_;
int res = 0;
while (bfs())
fill(cur, cur + t + 1, 0), res += dfs(s, inf);
return res;
}
void clear()
{
for (int i = 0; i <= t * 2; i++)
e[i].clear();
edges.clear();
}
}
namespace euler
{
vector<pii> e[maxn];
int ans[maxn], tot, deg[maxn]; // cd - rd
int virtual_node;
inline void add(int x, int y, int id)
{
e[x].emplace_back(y, id);
deg[x]++, deg[y]--;
}
void clear()
{
for (int i = 1; i <= virtual_node + 5; i++)
e[i].clear(), deg[i] = 0;
tot = 0;
}
void dfs(int x)
{
while (e[x].size())
{
auto &p = e[x].back();
int v = p.first, id = p.second;
e[x].pop_back();
dfs(v);
if (id)
ans[++tot] = id;
}
}
}
int notc[maxn]; // not satisfy C
int rd[maxn], cd[maxn];
void clear()
{
flow::clear();
euler::clear();
mp.clear();
for (int i = 1; i <= n * 2 + 5; i++)
rd[i] = cd[i] = 0;
for (int i = 1; i <= m; i++)
notc[i] = 0;
}
void main()
{
clear();
cin >> n >> m;
euler::virtual_node = n * 2 + 3;
for (int i = 1; i <= n; i++)
{
string s;
cin >> s, mp[s] = i;
}
int ans = 0;
map<pii, vector<int>> pos;
for (int i = 1; i <= m; i++)
{
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
int x = mp[s1], y = mp.count(s2) ? mp[s2] : 0, type = 0;
if (s3 == loushang && y)
type = 1, ans++;
else if (s3 == louxia && y)
type = 2, swap(x, y), ans++;
all[i].x = x, all[i].y = y, all[i].type = type;
}
for (int i = 1; i <= m; i++)
if (all[i].type == 1)
pos[pii(all[i].x, all[i].y)].push_back(i);
for (int i = 1; i <= m; i++)
if (all[i].type == 2)
{
auto p = pii(all[i].x, all[i].y);
if (!pos.count(p))
continue;
auto &arr = pos[p];
if (!arr.empty())
{
int j = arr.back();
arr.pop_back();
notc[i] = notc[j] = 1, rd[all[j].y + n]++, cd[all[j].x]++;
euler::virtual_node++;
euler::add(all[j].x, euler::virtual_node, j);
euler::add(euler::virtual_node, all[j].y + n, i);
}
}
for (int i = 1; i <= m; i++)
if (!notc[i])
{
if (all[i].type == 0)
rd[all[i].x + n]++, cd[all[i].x]++;
else if (all[i].type == 1)
cd[all[i].x]++, rd[all[i].y]++;
else
cd[all[i].x + n]++, rd[all[i].y + n]++;
}
int S = n * 2 + 5, T = S + 1;
for (int i = 1; i <= n; i++)
if (rd[i] > cd[i])
flow::add(S, i, rd[i] - cd[i]);
for (int i = n + 1; i <= n + n; i++)
if (cd[i] > rd[i])
flow::add(i, T, cd[i] - rd[i]);
vector<int> id(m + 10);
for (int i = 1; i <= m; i++)
if (!notc[i])
{
if (all[i].type == 1)
id[i] = flow::add(all[i].y, all[i].x + n, 1);
else if (all[i].type == 2)
id[i] = flow::add(all[i].y, all[i].x + n, 1);
}
ans -= flow::dinic(S, T); // 减去舍弃的边
for (int i = 1; i <= m; i++)
{
if (notc[i])
continue;
if (all[i].type == 1 && flow::edges[id[i]].now_flow() == 0)
all[i].type = 0;
if (all[i].type == 2 && flow::edges[id[i]].now_flow() == 0)
all[i].type = 0, swap(all[i].x, all[i].y);
if (all[i].type == 0)
euler::add(all[i].x, all[i].x + n, i);
else if (all[i].type == 1)
euler::add(all[i].x, all[i].y, i);
else
euler::add(all[i].x + n, all[i].y + n, i);
}
int aux_node = n * 2 + 1;
for (int i = 1; i <= n; i++)
{
while (euler::deg[i] > 0)
euler::add(aux_node, i, 0);
while (euler::deg[i] < 0)
euler::add(i, aux_node, 0), ans--; // 减去无法匹配的边
}
for (int i = n + 1; i <= n + n; i++)
{
while (euler::deg[i] > 0)
euler::add(aux_node, i, 0), ans--;
while (euler::deg[i] < 0)
euler::add(i, aux_node, 0);
}
cout << ans << endl;
euler::dfs(aux_node);
reverse(euler::ans + 1, euler::ans + 1 + m);
for (int i = 1; i <= m; i++)
cout << euler::ans[i] << " ";
cout << endl;
}
}