对于这种有很多相交的二元限制，可以考虑建图。
对于 \((a_i,b_i)\)，连无向边 \((a_i,b_i)\)，得到 \(N\) 个点，\(M\) 条边的无向图。对于一条边 \((a_i,b_i)\)，称 \(a_i\) 是这条边的 \(\mathrm{A}\) 端，\(b_i\) 是这条边的 \(\mathrm{B}\) 端。
注意到，对于每个 \(M\) 的排列 \(p_{1\sim M}\)，如果合法，最后第 \(i\) 个人拿到的商品为 \(x_i\)，那么每个合法的 \(p\) 会对应唯一的 \(x\)（很显然，也很重要）。所以考虑对于每个可能的 \(x\) 去计算有多少种取到 \(x\) 的 \(p\)。对应到图上，就是要让每条边匹配它的一个端点。
每个连通块之间独立，可以分别计算，最后组合数合并。下面只考虑一个 \(n\) 个点，\(m\) 条边的连通图。
对于 \(m>n\)，显然不可能让每条边匹配一个不同的端点，故方案数为 \(0\)。
对于 \(m=n-1\)，图是一棵树。此时最后一定会有恰好一个点没有匹配，将其作为树根，设为 \(rt\)。对于 \(rt\)，要求它一定是所有与它相邻的边的 \(\mathrm{B}\) 端。然后可以发现，对于每条边 \(i\)，它匹配的端点一定是 \(a_i,b_i\) 中深度较深的那个。如果是 \(b_i\)，那么匹配 \(a_i\) 的那条边一定要在 \(i\) 之前；如果是 \(a_i\)，可以发现只要限制了所有 \(x_i=b_i\) 的边，这些边就会自然地取到 \(a_i\)。
所以考虑再建一张有向图，对于每个 \(x_i=b_i\) 的 \(i\)，连有向边 \(a_i\to b_i\)，表示匹配 \(a_i\) 的边要在匹配 \(b_i\) 的边之前，那么合法的排列 \(p\) 的数量就是有向图的拓扑序。可以发现，每条边一定是原树上的父亲指向儿子，所以这一定是一个 \(n-1\) 个点（去掉了 \(rt\)）的外向森林，拓扑序易求。这样可以 \(\mathcal O(n)\) 对于一个特定的 \(rt\) 求出答案。换根 dp 即可 \(\mathcal O(n)\) 对每个 \(rt\) 求出答案。
对于 \(m=n\)，图是基环树。将环作为根，那么每条不在环上边也只能匹配深度较深的端点。设环上的点按顺序为 \(u_1,u_2,\dots,u_k\)，那么环上边整体只有两种可能：要么所有 \((u_i,u_{(i\bmod k) + 1})\) 都匹配 \(u_i\)，要么都匹配 \(u_{(i\bmod k) + 1}\)。所以 \(x\) 只有两种。
对于每种 \(x\)，同上建有向图。可以发现对于不在环上的边，对应的有向边一定是从父亲指向儿子。对于环上的边，一定同时是 \(u_i\) 指向 \(u_{(i\bmod k) + 1}\) 或同时是 \(u_{(i\bmod k) + 1}\) 指向 \(u_i\)。而且注意到，如果 \(k\) 条环上边都对应了有向边，说明所有环上边都匹配到了 \(\mathrm{B}\) 端，这是不可能的，所以此时答案为 \(0\)。可以发现排除这种情况后，得到的有向图一定是一个 \(n\) 个点的外向森林，容易计算拓扑序。这部分复杂度也为 \(\mathcal O(n)\)。
总复杂度 \(\mathcal O(n)\)。