首先对问题进行转化。构造 n + m 个点的有向图 G：将 (x, y, R) 操作视为向 G 中加入 y + n \to x 的有向边，将 (x, y, C) 视为加入 x \to y + n 的有向边，并要求在每次加边时两端点入度均为 0。此时，k 即为 G 的边数，答案即为 G 的数量。接下来，我们将借助这一构造说明 k = n + m - 1。
首先说明 k \le n + m - 1。将 G 视作无向图，下面将说明，G 中必然不存在环。考虑反证，如果图中存在环 (C_1, C_2), (C_2, C_3), \cdots, (C_k, C_1)，不妨设 (C_1, C_2) 的方向为 C_1 \to C_2，那么 (C_2, C_3) 的方向就只能为 C_2 \to C_3，否则 C_1 \to C_2 与 C_3 \to C_2 无论谁先谁后都会导出矛盾……以此类推，一直到 (C_k, C_1) 的方向只能为 C_k \to C_1。不妨设 (C_1, C_2) 是环中最后一个被操作的边，在它被操作前，(C_k, C_1) 已经被定向为 C_k \to C_1，C_1 的入度不为 0，从而导出矛盾。因此，将 G 视为无向图后其中不存在环，即有 k \le n + m - 1。
接下来说明 k = n + m - 1 能够取到。此时将 G 视为无向图，其必然为一棵树。而在刚刚的证明过程中，我们发现，在最终的定向结果中，不能同时存在 x \to z 和 y \to z 这样的两条边。这也就意味着最终每个点的入度都不超过 1。而入度的总和为 n + m - 1，这就说明恰有 1 个点（记其为 x）入度为 0，剩余的点入度恰为 1——实际上，这就是一颗以 x 为根的外向树。而对于这样一颗外向树，我们只需不断操作叶子结点的连边，即可满足连边时两端点入度为 0 的限制。因此，每一棵外向树都是可行的，k 自然可以取到 n + m - 1。
至此，我们已经可以顺理成章地得到计数做法。注意到在外向树根节点的选择中，每个点都是可行的，因此每颗树都可以衍生出 (n + m) 个不同的外向树。哪些树是可行的呢？不难发现，K_{n, m} 的每一颗生成树均可行。而 K_{n, m} 的生成树个数是一个经典问题，展开行列式即可知其答案为 n ^ {m - 1} m ^ {n - 1}，故原问题答案即为 f(n, m) = (n + m) n ^ {m - 1} m ^ {n - 1}。预处理 i ^ j 并计算，复杂度即为 O(nm)。