题目保证存在一种合法方案，我们可以考虑由一个合法方案怎么调整出不同的合法方案。

为了方便理解，我们钦定优先向左遍历，把换向操作转换成翻转子树的操作。

容易发现，翻转一棵子树时已经合法匹配的点不受影响，那么只有那些当前未配对的点需要考虑。跟虚树的角度差不多，我们把这些子树内已经匹配上的点踢掉分析。

分析问题的重要方法：从小入手。

两种颜色

$X$ 和 $Y$ 子树内都有一个 $A$ 和一个 $B$ 颜色节点没有参与匹配，翻转点 $X$ 后应该翻转 $Y$ 才能构成新的合法结构。

$Y$ 子树内只有 $A_1$ 没有匹配，可以随意翻转；而 $X$ 翻转后无法通过翻转其他节点构成合法结构。

可以发现，对于一个合法序列，翻转一部分，如果这个部分中至少有两个未匹配的点，那么必须将对应区间也翻转，或者在其他点把这个部分翻转回来。

那假如我们已经翻转了一个部分，到底翻转哪些点才能转回合法？

两个不够具有普适性，我们引入第三个节点。

三种颜色

翻转 $Y$ 后，$Z$ 和 $W$ 都可以把 $A_2,B_2$ 相对位置调整正确，然而这会使得 $C_2$ 调到中间不再合法，因此只能翻转 $W$。

通过上述的分析，我们发现，翻转了一个点 $u$，就必须翻转树上管辖着一模一样的 $S$ 的 $v$。

至此我们可以得出结论：设 $S_u$ 为 $u$ 子树内未匹配节点集合。若 $|S_u| \geq 2$，则当且仅当 $S_u=S_v \ (u \neq v)$，可以通过同时翻转子树 $u, v$ 得出新的合法方案。若 $|S_u|=1$，那怎么样翻转都行。

怎么计数？设等价类 $A_k$ 包含了所有 $S$ 相同，且 $|S| \geq 2$ 的点，等价类共有 $m$ 个。设 $|S|=1$ 的点有 $t$ 个。每个等价类我们都可以任选偶数个翻转，则：

$$ans=2^t\prod_{k=1}^{m}\sum_{i=0}^{|A_k|/2} \binom{|A_k|}{2i}=2^t\prod_{k=1}^{m}2^{|A_k|-1}=2^{2n-1-m} $$

问题转化为计算等价类的个数。

第 $i$ 次操作加入颜色 $i$，下标不仅是元素编号，也表示了时间，务必记住这一点。

用 01 序列表示集合 $S_u$。若两 01 序列的 lcp 长度为 $l$，则说明在前 $l$ 次操作里它们都属于同一个等价类！

使用树上差分标记修改，显然可以用线段树高效维护合并集合。至此我们得到了每个点子树内的未匹配点集，我们把这些字符串记为 $a[i]$。

已知所有集合，如何计数等价类？

对所有字符串按字典序排序后（比较操作就是查询 lcp，这可以通过对比两棵线段树上区间哈希值来实现，单次对比复杂度是 $O(\log n)$ 的），若 $\text{lcp}(a[i-1], a[i])=L$，这意味着在 $L+1$ 时新出现了一个等价类。

由于更长的 lcp 覆盖了短的 lcp，如果字符串 $\text{lcp}(a[i], a[j]) \leq \text{lcp}(a[i], a[i-1])$，那么在 $i-1$ 或更早，$a[i], a[j]$ 分歧产生的新等价类已经被计数过了。所以这就覆盖了所有的情况，避免了冗余的比较。

Code

有点难写啊，空间有点玄学，瞎开的。

#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN = 2e6;
const int MAXB = 24;
int c, n;
int lc[MAXN], rc[MAXN];
int fa[25][MAXN], depth[MAXN], pw131[MAXN], ans[MAXN];
vector<int> add[MAXN], del[MAXN];
struct Mergeable_Segment_Tree {
	struct Node {
		int h, pos1, pos2;
		int lc, rc;
		Node() {
			h = lc = rc = 0;
			pos1 = pos2 = 1e9;
		}
	};
	Node tr[int(2e7)];
	int root[MAXN], tot;
	void push_up(int p, int l, int r) {
		int mid = (l + r) >> 1;
		tr[p].h = (tr[tr[p].lc].h * pw131[r - mid] + tr[tr[p].rc].h) % MOD;
		if (tr[tr[p].lc].pos1 == 1e9) {
			tr[p].pos1 = tr[tr[p].rc].pos1;
			tr[p].pos2 = tr[tr[p].rc].pos2;
		} else {
			tr[p].pos1 = tr[tr[p].lc].pos1;
			if (tr[tr[p].lc].pos2 != 1e9) tr[p].pos2 = tr[tr[p].lc].pos2;
			else tr[p].pos2 = tr[tr[p].rc].pos1;
		}
	}
	int update(int p, int l, int r, int pos, int k) {
		int q = ++tot;
		tr[q] = tr[p];
		if (l == r) {
			tr[q].h = k;
			tr[q].pos1 = (k ? l : 1e9);
			tr[q].pos2 = 1e9;
			return q;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) tr[q].lc = update(tr[p].lc, l, mid, pos, k);
		else tr[q].rc = update(tr[p].rc, mid + 1, r, pos, k);
		push_up(q, l, r);
		return q;
	}
	int merge(int p1, int p2, int l, int r) {
		if (!p1 || !p2) return p1 ? p1 : p2;
		int p = ++tot;
		if (l == r) {
			tr[p].h = (tr[p1].h + tr[p2].h) % MOD;
			tr[p].pos1 = min(tr[p1].pos1, tr[p2].pos1);
			tr[p].pos2 = 1e9;
			return p;
		}
		int mid = (l + r) >> 1;
		tr[p].lc = merge(tr[p1].lc, tr[p2].lc, l, mid);
		tr[p].rc = merge(tr[p1].rc, tr[p2].rc, mid + 1, r);
		push_up(p, l, r);
		return p;
	}
	pair<int, int> lcp(int p1, int p2, int l, int r) {
		if (tr[p1].h == tr[p2].h) return make_pair(n + 1, 1);
		if (!p1) return make_pair(tr[p2].pos1, 2);
		if (!p2) return make_pair(tr[p1].pos1, 1);
		if (l == r) return make_pair(l, !tr[p1].h ? 2 : 1);
		int mid = (l + r) >> 1;
		if (tr[tr[p1].lc].h != tr[tr[p2].lc].h) return lcp(tr[p1].lc, tr[p2].lc, l, mid);
		else return lcp(tr[p1].rc, tr[p2].rc, mid + 1, r);
	}
};
Mergeable_Segment_Tree mst;
void dfs(int x) {
	if (!x) return;
	for (int i = 1; i <= MAXB; ++i) {
		fa[i][x] = fa[i - 1][fa[i - 1][x]];
	}
	if (lc[x]) {
		fa[0][lc[x]] = x;
		depth[lc[x]] = depth[x] + 1;
		dfs(lc[x]);
	}
	if (rc[x]) {
		fa[0][rc[x]] = x;
		depth[rc[x]] = depth[x] + 1;
		dfs(rc[x]);
	}
}
inline int lca(int x, int y) {
	if (depth[x] != depth[y]) {
		if (depth[x] < depth[y]) {
			swap(x, y);
		}
		for (int i = MAXB; i >= 0; --i) {
			if (depth[fa[i][x]] >= depth[y]) {
				x = fa[i][x];
			}
		}
	}
	if (x == y) return x;
	for (int i = MAXB; i >= 0; --i) {
		if (fa[i][x] != fa[i][y]) {
			x = fa[i][x];
			y = fa[i][y];
		}
	}
	return fa[0][x];
}
void dfs2(int x) {
	if (!x) return;
	dfs2(lc[x]);
	dfs2(rc[x]);
	mst.root[x] = mst.merge(mst.root[x], mst.root[lc[x]], 1, n);
	mst.root[x] = mst.merge(mst.root[x], mst.root[rc[x]], 1, n);
	for (int d : del[x]) {
		mst.root[x] = mst.update(mst.root[x], 1, n, d, 0);
	}
	for (int d : add[x]) {
		mst.root[x] = mst.update(mst.root[x], 1, n, d, 1);
	}
}
bool cmp(int p1, int p2) {
	return mst.lcp(p1, p2, 1, n).second == 2;
}
inline int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = (res * a) % MOD;
		a = (a * a) % MOD;
		b >>= 1;
	}
	return res;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> c >> n;
	depth[1] = 1;
	pw131[0] = 1;
	for (int i = 1; i <= n; ++i) {
		pw131[i] = (pw131[i - 1] * 131) % MOD;
	}
	for (int i = 1; i <= 2 * n - 1; ++i) {
		cin >> lc[i] >> rc[i];
	}
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		int a, b;
		cin >> a >> b;
		int l = lca(a, b);
		add[a].emplace_back(i);
		add[b].emplace_back(i);
		del[l].emplace_back(i);
	}
	dfs2(1);
	sort(mst.root + 1, mst.root + 2 * n, cmp);
	for (int i = 1; i <= 2 * n - 1; ++i) {
		if (mst.tr[mst.root[i]].pos2 != 1e9) { //新等价类对应S集合的元素个数必须大于1
			if (i == 1) ++ans[mst.tr[mst.root[1]].pos2];
			else
				++ans[max(mst.lcp(mst.root[i], mst.root[i - 1], 1, n).first, mst.tr[mst.root[i]].pos2)];
		}
	}
	for (int i = 1; i <= n; ++i) {
		ans[i] += ans[i - 1];
		cout << qpow(2, 2 * n - 1 - ans[i]) << endl;
	}
	return 0;
}