#include <bits/stdc++.h>
using namespace std;
#define ff endl
#define lf "\n"
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define infor(str, ...) do { fprintf(stderr, str, ##__VA_ARGS__); } while(0)
#define infof(str, ...) do { fprintf(stderr, str"\n", ##__VA_ARGS__); } while(0)
#ifndef DEBUG
#undef infor
#undef infof
#define infor(str, ...)
#define infof(str, ...)
#endif
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
constexpr int LOG = 8; // > LOG(200, 2)
constexpr int MOD = 1e9+7;
constexpr int MAXN = 1e5+7;
pii find_close_centroid(int N, int src, const vector<vector<int>> &adj) {
vector<int> sz(N), d(N + 1);
auto dfs = [&](int v, int f, auto &&dfs) -> void {
sz[v] = 1;
for(auto u: adj[v]) {
if(u == f) continue;
d[u] = 1 + d[v];
dfs(u, v, dfs);
sz[v] += sz[u];
}
};
dfs(src, -1, dfs);
d[N] = N + 1;
pii cand = {N, N};
auto find_centroid = [&](int v, int f, auto &&find_centroid) -> void {
for(auto u: adj[v]) {
if(u == f || 2 * sz[u] < N) continue; // note that N/2 rounds down
if(sz[u] == N / 2) {
cand = {u, v};
return;
}
return find_centroid(u, v, find_centroid);
}
cand.first = v;
};
find_centroid(src, -1, find_centroid);
if(d[cand.first] > d[cand.second]) swap(cand.first, cand.second);
return cand;
}
void solve(int N, int root, int root2, const vector<vector<int>> &adj,
int src, vector<int> &ans, bool is_bruno) {
ans.emplace_back(src);
set<int> alive;
vector<int> F(N), d(N);
auto dfs = [&](int v, auto &&dfs) -> void {
alive.emplace(v);
for(auto u: adj[v]) {
if(u == F[v]) continue;
F[u] = v;
d[u] = 1 + d[v];
dfs(u, dfs);
}
};
F[root] = root2;
dfs(root, dfs);
F[root] = root;
alive.erase(root);
int mx_size = 1;
for(int lg = 0; lg < LOG; ++lg) {
infof("===== lg = %d =====", lg);
infof("... src = %d", src);
const int pow = 1 << lg;
vector<int> path;
vector<int> rm;
for(auto v: alive) {
if(d[v] % (2 * pow) == 0) continue;
rm.emplace_back(v);
}
for(auto v: rm) {
alive.erase(v);
}
if(src == root) {
if(root2 < N && is_bruno) {
ans.emplace_back(root2);
}
} else {
int u = src;
for(int i = 0; i < pow; ++i) {
u = F[u];
path.emplace_back(u);
}
if(alive.find(src) != alive.end()) {
for(auto v: path) {
ans.emplace_back(v);
}
}
}
mx_size += pow;
ans.resize(mx_size, ans.back());
if(root2 < N) {
if(src == root && is_bruno) {
ans.emplace_back(root);
}
mx_size++;
ans.resize(mx_size, ans.back());
}
if(src != root) {
if(d[src] % (2 * pow) == 0) {
infor("... path:");
for(auto x: path) {
infor(" %d", x);
}
infof("");
path.pop_back();
reverse(all(path));
path.emplace_back(src);
} else src = path.back();
for(auto v: path) {
ans.emplace_back(v);
}
}
mx_size += pow;
ans.resize(mx_size, ans.back());
}
}
vector<int> Aitana(int N, vector<int> A, vector<int> B, int src, int subtask) {
infof("----- Aitana -----");
infof("... N = %d | src = %d", N, src);
vector<vector<int>> adj(N);
for(int i = 0; i < N - 1; ++i) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
pii c = find_close_centroid(N, src, adj);
if(c.second < c.first) {
c.first = c.second;
} else c.second = c.first;
infof("... c = {%d, %d}", c.first, c.second);
vector<int> ans;
ans.reserve(10 * N + 1);
solve(N, c.first, c.second, adj, src, ans, 0);
ans.resize(10 * N + 1, ans.back());
infor("ans:");
for(auto x: ans) {
infor(" %d", x);
}
infof("");
return ans;
}
vector<int> Bruno(int N, vector<int> A, vector<int> B, int src, int subtask) {
infof("----- Bruno -----");
infof("... N = %d | src = %d", N, src);
vector<vector<int>> adj(N);
for(int i = 0; i < N - 1; ++i) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
pii c = find_close_centroid(N, src, adj);
if(c.second < c.first) {
c.first = c.second;
} else c.second = c.first;
infof("... c = {%d, %d}", c.first, c.second);
vector<int> ans;
ans.reserve(10 * N + 1);
solve(N, c.first, c.second, adj, src, ans, 1);
ans.resize(10 * N + 1, ans.back());
infor("ans:");
for(auto x: ans) {
infor(" %d", x);
}
infof("");
return ans;
}
#ifdef LOCAL
namespace {
const int INVALID_X_LENGTH = 1;
const int INVALID_X_RANGE = 2;
const int INVALID_X_START = 3;
const int INVALID_X_PATH = 4;
const int INVALID_Y_LENGTH = 5;
const int INVALID_Y_RANGE = 6;
const int INVALID_Y_START = 7;
const int INVALID_Y_PATH = 8;
const int INVALID_MEET = 9;
std::mt19937_64 mt;
int case_id;
void WrongAnswer(int code) {
printf("Case #%d: Wrong Answer [%d]\n", case_id, code);
}
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input.\n");
exit(1);
}
return x;
}
bool check_permutation(int N, const std::vector<int>& p) {
std::vector<bool> f(N, false);
for (int x : p) {
if (!(0 <= x && x < N)) return false;
if (f[x]) return false;
f[x] = true;
}
return true;
}
bool check_tree(int N, const std::vector<int>& u, const std::vector<int>& v) {
std::vector<std::vector<int>> G(N);
for (int i = 0; i < N - 1; i++) {
if (!(0 <= u[i] && u[i] < N)) {
return false;
}
if (!(0 <= v[i] && v[i] < N)) {
return false;
}
G[u[i]].push_back(v[i]);
G[v[i]].push_back(u[i]);
}
std::vector<bool> vis(N, false);
std::vector<int> st = {0};
vis[0] = true;
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int i : G[u]) {
if (!vis[i]) {
vis[i] = true;
st.push_back(i);
}
}
}
return (vis == std::vector<bool>(N, true));
}
std::string check_validness(int N, const std::vector<int>& u,
const std::vector<int>& v,
const std::vector<int>& p,
const std::vector<int>& q, int s, int t,
int subtask) {
if (!(1 <= subtask && subtask <= 3)) return "1 <= subtask <= 3";
if (!check_permutation(N, p)) return "p is not a permutation";
if (!check_permutation(N, q)) return "q is not a permutation";
if (!check_tree(N, u, v)) return "(u, v) does not form a tree";
if (!(0 <= s && s < N && 0 <= t && t < N && s != t)) return "Invalid s or t";
if (subtask == 1) {
for (int i = 0; i < N; i++) {
if (!(p[i] == i && q[i] == i)) {
return "(p, q) does not meet the condition for subtask 1";
}
}
}
if (subtask == 2) {
for (int i = 0; i < N - 1; i++) {
if (!(u[i] == i && v[i] == i + 1)) {
return "(u, v) does not meet the condition for subtask 2";
}
}
}
return "";
}
void shuffle_edge(int M, std::vector<int>& u, std::vector<int>& v) {
for (int i = 0; i < M; i++) {
if (mt() % 2 == 1) {
std::swap(u[i], v[i]);
}
int x = mt() % (i + 1);
std::swap(u[i], u[x]);
std::swap(v[i], v[x]);
}
}
int tree_distance(int N, const std::vector<int>& u, const std::vector<int>& v,
int s, int t) {
std::vector<std::vector<int>> G(N);
for (int i = 0; i < N - 1; i++) {
G[u[i]].push_back(v[i]);
G[v[i]].push_back(u[i]);
}
std::vector<int> dist(N, -1);
dist[s] = 0;
std::queue<int> que;
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i : G[u]) {
if (dist[i] == -1) {
dist[i] = dist[u] + 1;
que.push(i);
}
}
}
return dist[t];
}
void run_scenario(int N, const std::vector<int>& u, const std::vector<int>& v,
const std::vector<int>& p, const std::vector<int>& q, int s,
int t, int subtask) {
std::vector<int> invp(N), invq(N);
for (int i = 0; i < N; i++) {
invp[p[i]] = i;
invq[q[i]] = i;
}
infor("invp [A]:");
for(auto i: invp) {
infor(" %d", i);
}
infof("");
infor("invq [B]:");
for(auto i: invq) {
infor(" %d", i);
}
infof("");
std::vector<int> A(N - 1), B(N - 1), C(N - 1), D(N - 1);
std::vector<std::pair<int, int>> edges(N - 1);
for (int i = 0; i < N - 1; i++) {
A[i] = p[u[i]];
B[i] = p[v[i]];
C[i] = q[u[i]];
D[i] = q[v[i]];
edges[i] = std::minmax({u[i], v[i]});
}
shuffle_edge(N - 1, A, B);
shuffle_edge(N - 1, C, D);
int S = p[s];
int T = q[t];
std::sort(edges.begin(), edges.end());
auto adjacent = [&](int a, int b) -> bool {
return std::binary_search(edges.begin(), edges.end(), std::minmax({a, b}));
};
#ifdef DEBUG
std::fprintf(stderr, "===== START OF TEST =====\n");
#endif
std::vector<int> x = Aitana(N, A, B, S, subtask);
if (int(x.size()) != 10 * N + 1) return WrongAnswer(INVALID_X_LENGTH);
for (int i = 0; i <= 10 * N; i++) {
if (!(0 <= x[i] && x[i] < N)) return WrongAnswer(INVALID_X_RANGE);
}
if (!(x[0] == S)) return WrongAnswer(INVALID_X_START);
for (int i = 0; i < 10 * N; i++) {
if (!(x[i] == x[i + 1] || adjacent(invp[x[i]], invp[x[i + 1]]))) {
return WrongAnswer(INVALID_X_PATH);
}
}
std::vector<int> y = Bruno(N, C, D, T, subtask);
if (int(y.size()) != 10 * N + 1) {
return WrongAnswer(INVALID_Y_LENGTH);
}
for (int i = 0; i <= 10 * N; i++) {
if (!(0 <= y[i] && y[i] < N)) {
return WrongAnswer(INVALID_Y_RANGE);
}
}
if (!(y[0] == T)) return WrongAnswer(INVALID_Y_START);
for (int i = 0; i < 10 * N; i++) {
if (!(y[i] == y[i + 1] || adjacent(invq[y[i]], invq[y[i + 1]]))) {
return WrongAnswer(INVALID_Y_PATH);
}
}
int meet = -1;
for (int i = 0; i <= 10 * N; i++) {
if (invp[x[i]] == invq[y[i]]) {
meet = i;
break;
}
}
if (meet == -1) {
infof("----- Grader -----");
infor("Aitana:");
for(auto i: x) {
infor(" %d", invp[i]);
}
infof("");
infor("Bruno:");
for(auto i: y) {
infor(" %d", invq[i]);
}
infof("");
return WrongAnswer(INVALID_MEET);
}
int dist = tree_distance(N, u, v, s, t);
printf("Case #%d: Accepted %d %d\n", case_id, meet, dist);
}
} // namespace
int main(int argc, char* argv[]) {
if (!(argc == 1 || argc == 2)) {
fprintf(stderr, "usage: %s [<seed>]", argv[0]);
exit(1);
}
if (argc == 2) {
try {
const long long seed = std::stoll(argv[1]);
mt = std::mt19937_64(seed);
} catch (const std::exception& e) {
fprintf(stderr, "Invalid seed: %s\n", argv[1]);
exit(1);
}
}
int subtask = read_int();
int Q = read_int();
std::vector<int> N(Q), s(Q), t(Q);
std::vector<std::vector<int>> p(Q), q(Q), u(Q), v(Q);
for (int i = 0; i < Q; i++) {
N[i] = read_int();
u[i].resize(N[i] - 1);
v[i].resize(N[i] - 1);
for (int j = 0; j < N[i] - 1; j++) {
u[i][j] = read_int();
v[i][j] = read_int();
}
p[i].resize(N[i]);
q[i].resize(N[i]);
for (int& x : p[i]) x = read_int();
for (int& x : q[i]) x = read_int();
s[i] = read_int();
t[i] = read_int();
}
for (int i = 0; i < Q; i++) {
std::string err =
check_validness(N[i], u[i], v[i], p[i], q[i], s[i], t[i], subtask);
if (!err.empty()) {
fprintf(stderr, "Input does not satisfy the constraints: %s\n",
err.c_str());
exit(1);
}
}
for (int i = 0; i < Q; i++) {
case_id = i;
run_scenario(N[i], u[i], v[i], p[i], q[i], s[i], t[i], subtask);
}
return 0;
}
#endif
