sweet tea.
手玩一下发现「交换」的性质是具有传递性的，所以考虑一个 \(O(n^2)\) 做法：
枚举每个点对，如果满足交换条件，则连双向边。显然一个连通块内的点可以互相交换，而不同连通块之间互相独立。答案就是 \(\prod\limits_{i=1}^m\dbinom{size_i}{s_{i,1}\ s_{i,2}\ ...\ s_{i,n}}\)。 \(s_{i,j}\) 表示连通块 \(i\) 内颜色为 \(j\) 的点的数量。本质上就是个可重排列。
很可惜，这是 AGC D，暴力过不了。
充分发扬人类智慧，我们发现这个图点数很小，但是边数很大。最后求解答案的复杂度是 \(O(n+m)\) 的。我们又发现连出去的许多边是没有必要的，因为对于一个连通块，我们尽可能地只保留一个生成树，或者边数尽量少的结构，于是我们考虑如何减少重复的边。
第一种操作，每种颜色 \(c\) 分开考虑。对于颜色 \(c\) 的所有点，拎出一个 \(w\) 值最小的 \(w_{\min}\)。考虑同样是颜色 \(c\) 的 \((i,j)\) 满足 \(w_i+w_j\le x\)，那么显然有 \(w_i+w_{\min}\le x\) 并且 \(w_j+w_{\min}\le x\)，也就是说 \(i\) 到 \(j\) 的边是没有必要的。于是我们可以每个点向其同样颜色 \(w\) 值最小的点连边，边数 \(O(n)\)。
第二种操作，我们将所有颜色 \(\text{col}\) 按照 \(a_{\text{col}}=\min\limits_{c_i=\text{col}}w_i\) 从小到大排序。同上，我们考虑满足 \(c_i\neq c_j,w_i+w_j\le y\) 的 \((i,j)\)，但是为了避免 \(i,j\) 中有颜色和 \(a_\text{col}\) 最小值颜色 \(c_{\min}\) 相同，我们还需要拎出来一个次小值颜色 \(c_{\min_2}\) 来讨论（以下写点对颜色 \(c\) 连边，实际上是对颜色 \(c\) 中权值最小的点连边）：
- 若 \(c_i\ne c_{\min},c_j\neq c_{\min}\)，则不连 \((i,j)\)，将 \(i,j\) 都连向 \(c_{\min}\) 连边即可。
- 若 \(c_i\neq c_{\min_2},c_j\neq c_{\min_2}\)，也可以不连 \((i,j)\)，将 \(i,j\) 均连向 \(c_{\min_2}\) 即可。
- 否则 \(c_i\) 和 \(c_j\) 中必定有一个 \(c_{\min}\) 和一个 \(c_{\min_2}\)，不妨假设 \(c_i=c_{\min},c_j=c_{\min_2}\)，由于 \(w_i+w_j\le y\)，所以有 \(a_{\min}+a_{\min_2}\le y\)，两个最小值连边。再连 \((c_{\min},j)\) 和 \((c_{\min_2},i)\) 即可。
所以我们每个点，只需要考虑向最小值和次小值连边即可。边数 \(O(n)\)。
统计答案的话一个连通块显然不能求出连通块所有颜色个数后再计算答案，可以预处理阶乘 \(f_i\) 和阶乘的逆元 \(g_i\)，到达 \(c_u\) 时考虑 \(\text{ans}\) 的变化量，然后就随便做了。