#include <bits/stdc++.h>
#include "testlib.h"
 
using namespace std;

void shuffle_graph(int n, vector<pair<int, int>> & g) {
	int shift = rnd.next(0, n - 1);
	for (auto & p : g) {
		if (rnd.next(0, 1)) {
			swap(p.first, p.second);
		}
		p.first += shift;
		if (p.first >= n) {
			p.first -= n;
		}
		p.second += shift;
		if (p.second >= n) {
			p.second -= n;
		}
	}
	shuffle(g.begin(), g.end());
	if (rnd.next(0, 1)) {
		for (auto & p : g) {
			p.first = n - 1 - p.first;
			p.second = n - 1 - p.second;
		}
	}
}

void sort_graph(vector<pair<int, int>> & g) {
	for (auto & p : g) {
		if (p.first > p.second) {
			swap(p.first, p.second);
		}
	}
	sort(g.begin(), g.end());
}

void print(int n, int k, vector<pair<int, int>> & g, bool shuffle=true, bool sorted=false) {
	if (shuffle) {
		shuffle_graph(n, g);
	}
	if (sorted) {
		sort_graph(g);
	}
	cout << n << " " << g.size() << " " << k << "\n";
	for (auto p : g) {
		cout << min(p.first, p.second) + 1 << " " << max(p.first, p.second) + 1 << "\n";
	}
}

vector<int> gen_points(int n, int size) { 
	/* Returns size points on circle of size n with the distance at list 2.
	Always takes 0 for size > 0. */
    assert(2 * size <= n);
	if (size == 0) {
		return vector<int>{};
	}
	if (size == 1) {
		return vector<int>{0};
	}
	vector<int> steps = rnd.partition(size, n, 2);
	vector<int> points(size);
	for (int i = 0; i < size - 1; ++i) {
		points[i + 1] = points[i] + steps[i];
	}
	return points;
}

vector<int> gen_points_greedy(int n, int size) { 
	/* Returns size points on circle of size n with the distance 2 and one large skip.
	Always takes 0 for size > 0. */
	assert(2 * size <= n);
	if (size == 0) {
		return vector<int>{};
	}
	if (size == 1) {
		return vector<int>{0};
	}
	int t = rnd.next(0, size - 1);
	vector<int> points(size);
	for (int i = 0; i <= t; ++i) {
		points[i] = 2 * i;
	}
	for (int i = size - 1; i > t; --i) {
		points[i] = n - 2 - 2 * (size - 1 - i);
	}
	return points;
}

vector<int> gen_points_part_greedy(int n, int size, double big_ratio) { 
	/* Returns size points on circle of size n with the distance 2 and one large skip.
	Always takes 0 for size > 0. */
	assert(2 * size <= n);
	if (size == 0) {
		return vector<int>{};
	}
	if (size == 1) {
		return vector<int>{0};
	}
	vector<bool> big_step(size);
	for (int i = 0; i < size; ++i) {
		big_step[i] = rnd.next() < big_ratio;
	}
	int t = rnd.next(0, size - 1);
	big_step[t] = 1;
	int skips = 0;
	for (int i = 0; i < size; ++i) {
		skips += big_step[i];
	}
	vector<int> steps = rnd.partition(skips, n - 2 * (size - skips), 2);
	int j = 0;
	vector<int> points(size);
	for (int i = 0; i + 1 < size; ++i) {
		if (big_step[i]) {
			points[i + 1] = points[i] + steps[j++];
		} else {
			points[i + 1] = points[i] + 2;
		}
	}
	return points;
}

void map_graph(vector<int> & points, vector<pair<int, int>> & g) {
	for (auto & p : g) {
		p.first = points[p.first];
		p.second = points[p.second];
	}
}

int vertices(vector<pair<int, int>> & g) {
    int ans = 0;
    for (auto p : g) {
        ans = max(ans, p.first + 1);
        ans = max(ans, p.second + 1);
    }
    return ans;
}

void compress_graph(vector<pair<int, int>> & g) {
	int m = g.size();
	vector<int> number(2 * m);
	for (auto p : g) {
		number[p.first] = 1;
		number[p.second] = 1;
	}
	for (int i = 0; i < 2 * m - 1; ++i) {
		number[i + 1] += number[i];
	}
	for (auto & p : g) {
		p.first = number[p.first] - 1;
		p.second = number[p.second] - 1;
	}
}

vector<pair<int, int>> build_graph(vector<int> & pr, vector<vector<int>> & g) {
	int m = pr.size();
	vector<int> xs_v(2 * m);
	for (int i = 0; i < 2 * m; ++i) {
		xs_v[i] = i;
	}
	int T = 0;
	vector<pair<int, int>> segs(m);
	function<void(int)> Dfs = [&](int i) {
		segs[i].first = xs_v[T++];
		for (int j : g[i]) {
			Dfs(j);
		}
		segs[i].second = xs_v[T++];
	};
	for (int i = 0; i < m; i++) {
		if (pr[i] == -1) {
			Dfs(i);
		}
	}
	assert(T == 2 * m);
	return segs;
}

vector<pair<int, int>> build_graph_dir(vector<int> & pr, vector<vector<int>> & g, double prob, boolean dir=false, boolean left=true) {
	auto segs = build_graph(pr, g);
	int m = pr.size();
	function<void(int)> Dfs = [&](int i) {
		if (g[i].size() == 1) {
			if (!dir) {
				left = rnd.next(0, 1);
			}
			if (rnd.next() < prob) {
				if (left) {
					segs[g[i][0]].first = segs[i].first;
				} else {
					segs[g[i][0]].second = segs[i].second;
				}
			}
			Dfs(g[i][0]);
			return;
		}
		for (int id = 0; id < g[i].size(); ++id) {
			int j = g[i][id];
			if (id == 0 && rnd.next() < prob) {
				segs[j].first = segs[i].first;
			}
			if (id > 0 && rnd.next() < prob) {
				segs[j].first = segs[g[i][id - 1]].second;
			}
			if (id + 1 == g[i].size() && rnd.next() < prob) {
				segs[j].second = segs[i].second;
			}
			Dfs(j);
		}
	};
	int last = 0;
	for (int i = 0; i < m; i++) {
		if (pr[i] == -1) {
			if (rnd.next() < prob) {
				segs[i].first = last;
			}
			Dfs(i);
			last = segs[i].second;
		}
	}
	compress_graph(segs);
	return segs;
}

vector<pair<int, int>> build_graph_priority(vector<int> & pr, vector<vector<int>> & g, double prob) {
	auto segs = build_graph(pr, g);
	int m = pr.size();
	vector<int> priority = rnd.perm(2 * m);
	function<void(int)> Dfs = [&](int i) {
		if (g[i].size() == 1) {
			if (rnd.next() < prob) {
				if (min(priority[segs[i].first], priority[segs[g[i][0]].first]) 
						< min(priority[segs[i].second], priority[segs[g[i][0]].second])) {
					segs[g[i][0]].first = segs[i].first;
					priority[segs[i].first] = min(priority[segs[i].first], priority[segs[g[i][0]].first]);
				} else {
					segs[g[i][0]].second = segs[i].second;
					priority[segs[i].second] = min(priority[segs[i].second], priority[segs[g[i][0]].second]);
				}
			}
			Dfs(g[i][0]);
			return;
		}
		for (int id = 0; id < g[i].size(); ++id) {
			int j = g[i][id];
			if (id == 0 && rnd.next() < prob) {
				segs[j].first = segs[i].first;
			}
			if (id > 0 && rnd.next() < prob) {
				segs[j].first = segs[g[i][id - 1]].second;
			}
			if (id + 1 == g[i].size() && rnd.next() < prob) {
				segs[j].second = segs[i].second;
			}
			Dfs(j);
		}
	};
	int last = 0;
	for (int i = 0; i < m; i++) {
		if (pr[i] == -1) {
			if (rnd.next() < prob) {
				segs[i].first = last;
			}
			Dfs(i);
			last = segs[i].second;
		}
	}
	compress_graph(segs);
	return segs;
}

auto GenRandom(int m, int min_d, int max_d) {
	vector<int> pr(m);
	vector<vector<int>> g(m);
	for (int i = 0; i < m; i++) {
		pr[i] = (min_d == -1 ? rnd.next(-1, min(i - 1, max_d - 2)) : i - rnd.next(min(min_d, i + 1), min(max_d, i + 1)));
		if (pr[i] != -1) {
			g[pr[i]].push_back(i);
		}
	}
	return pair{pr, g};
};

auto GenSpecial(int id, int m) {
	vector<int> pr(m, -1);
	vector<vector<int>> g(m);
	if (id == 1) {
		for (int i = 0; i < m - 1; ++i) {
			pr[i + 1] = i;
			g[i].push_back(i + 1);
		}
	} else if (id == 2) {
	} else if (id == 3) {
		for (int i = 0; i < m / 2 - 1; ++i) {
			pr[i + 1] = i;
			g[i].push_back(i + 1);
		}
		for (int i = 0; i < m / 4; ++i) {
			pr[m / 2 + 2 * i] = m / 2 - 1;
			g[m / 2 - 1].push_back(m / 2 + 2 * i);
			pr[m / 2 + 2 * i + 1] = m / 2 + 2 * i;
			g[m / 2 + 2 * i].push_back(m / 2 + 2 * i + 1);
		}
	} else if (id == 4) 	{
		int ptr = 0;
		for (int i = 0; i < m / 2; i++) {
			pr[2 * i] = 2 * i - 1;
			pr[2 * i + 1] = 2 * i - 1;
			if (i > 0) {
				g[2 * i - 1].push_back(2 * i);
				g[2 * i - 1].push_back(2 * i + 1);
			}
		}
	} else if (id == 5) {
		int ptr = 0;
		for (int i = 0; i < m / 4; i++) {
			pr[4 * i] = 4 * i - 1;
			pr[4 * i + 3] = 4 * i - 1;
			if (i > 0) {
				g[4 * i - 1].push_back(4 * i);
				g[4 * i - 1].push_back(4 * i + 3);
			}
			pr[4 * i + 1] = 4 * i;
			pr[4 * i + 2] = 4 * i;
			g[4 * i].push_back(4 * i + 1);
			g[4 * i].push_back(4 * i + 2);
		}
	} else {
		throw;
	}
	return pair{pr, g};
};

auto GenDeepRandom(int m, int depth, int max_d) {
	vector<int> pr(m);
	vector<vector<int>> g(m);
	for (int i = 0; i < m; i++) {
		pr[i] = (i <= depth ? i - 1 : i - rnd.next(1, min(max_d, i - depth)));
		if (pr[i] != -1) {
			g[pr[i]].push_back(i);
		}
	}
	return pair{pr, g};
};

auto GenDeepUndeep(int m, int depth, double coeff) {
	vector<int> pr(m);
	vector<vector<int>> g(m);
	int ptr = 0;
	for (int i = 0; i < m; i++) {
		if (i <= depth) {
			pr[i] = i - 1;
			ptr = i;
		} else {
			if (rnd.next() < coeff) {
				pr[i] = depth;
				ptr = i;
			} else {
				pr[i] = i - rnd.next(1, i - ptr);
			}
		}
		if (pr[i] != -1) {
			g[pr[i]].push_back(i);
		}
	}
	return pair{pr, g};
};
