#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

// #define Debug

const int N = 1e5;
const long long P = 1e9 + 7;

int W, n, m;
int cnt = 2;//1-n, (n - 1)-n
long long ans = 1;

set<int> e[N + 5];

map<pair<int, int>, int> id;

long long fac[N + 5], inv[N + 5];
long long ksm(long long d, long long u)
{
	long long res = 1;
	while (u)
	{
		if (u & 1)
			res = res * d % P;
		u >>= 1;
		d = d * d % P;
	}
	return res;
}
void init()
{
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i % P;
	inv[n] = ksm(fac[n], P - 2);
	for (int i = n - 1; i >= 0; i--)
		inv[i] = inv[i + 1] * (i + 1) % P;
	return ;
}
long long C(int x, int y)//C_x^y
{
	if (x < y)
		return 0ll;
	return fac[x] * inv[y] % P * inv[x - y] % P;
}
long long invC(int x, int y)
{
	if (x < y)
		return 0ll;
	return inv[x] * fac[y] % P * fac[x - y] % P;
}

int ch[N + 5][2], fa[N + 5];
int sz[N + 5];
int build(int l, int r, int father)//l <= r
{
	if (l + 1 == r)
		return 0;

	int p = id[make_pair(l, r)];
	fa[p] = father;
	
	int split = *prev(e[l].find(r));
	ch[p][0] = build(l, split, p);
	ch[p][1] = build(split, r, p);

	sz[p] = sz[ch[p][0]] + 1 + sz[ch[p][1]];
	ans = ans * C(sz[p] - 1, sz[ch[p][0]]) % P;//C(sz(ls) + sz(rs), sz(ls))
	return p;
}
int sontype(int p)
{
	return p == ch[fa[p]][1];
}

void print(int ans1, long long ans2)
{
	if (W)
		printf("%d %lld\n", ans1, ans2);
	else
		printf("%d\n", ans1);
	return ;
}

int main()
{
	// freopen("polygon.in", "r", stdin);
	// freopen("polygon.out", "w", stdout);

	scanf("%d%d", &W, &n);
	for (int i = 1, x, y; i <= n - 3; i++)
	{
		scanf("%d%d", &x, &y);
		e[x].insert(y), e[y].insert(x);
		id[make_pair(x, y)] = id[make_pair(y, x)] = i;
		cnt += (x == n || y == n);
	}

	for (int i = 1; i < n; i++)
		e[i].insert(i + 1), e[i + 1].insert(i);
	e[n].insert(1), e[1].insert(n);

	init();
	int cur = 0;
	for (auto it = e[n].begin(), nxt = next(it); nxt != e[n].end(); it++, nxt++)
	{
		int l = *it, r = *nxt;
		build(l, r, 0);
		
		int p = id[make_pair(l, r)];
		cur += sz[p];
		ans = ans * C(cur, sz[p]) % P;//different tree
	}

	print(n - 1 - cnt, ans);
	scanf("%d", &m);
	for (int i = 1, x, y; i <= m; i++)
	{
		scanf("%d%d", &x, &y);
		if (x > y)
			swap(x, y);

		int nw_cnt = cnt;
		long long nw_ans = ans;
		int p = id[make_pair(x, y)];

		if (fa[p])
		{
			int type = sontype(p), bro = ch[ fa[p] ][type ^ 1];
			int szA = sz[ ch[p][type] ];
			int szB = sz[ ch[p][type ^ 1] ];
			int szC = sz[ bro ];

			nw_ans = nw_ans * invC(sz[p] - 1, szA) % P;
			nw_ans = nw_ans * invC(sz[fa[p]] - 1, szC) % P;

			nw_ans = nw_ans * C(szB + szC, szC) % P;
			nw_ans = nw_ans * C(sz[fa[p]] - 1, szA) % P;
		}
		else if (y < n)//(x, y) -> (?, n)
		{
			nw_cnt++;
			nw_ans = nw_ans * invC(cur, sz[p]) % P;//only edges that not connect to n, which is cur, not n - 3 !
		}
		else//(x, n) -> (?, ?)
		{
			nw_cnt--;
			
			auto it = e[n].find(x);
			int l = *prev(it), r = *next(it);
			int ls = id[make_pair(l, x)];
			int rs = id[make_pair(x, r)];
			nw_ans = nw_ans * C(sz[ls] + sz[rs], sz[ls]) % P;
		}

		print(n - 1 - nw_cnt, nw_ans);
	}
	return 0;
}