#include #include template struct Edge { int src, dst; Cost cost; Edge(int src = -1, int dst = -1, Cost cost = 1) : src(src), dst(dst), cost(cost){}; bool operator<(const Edge& e) const { return this->cost < e.cost; } bool operator>(const Edge& e) const { return this->cost > e.cost; } }; template struct Graph { std::vector>> graph; Graph(int n = 0) : graph(n) {} void span(bool direct, int src, int dst, Cost cost = 1) { graph[src].emplace_back(src, dst, cost); if (!direct) graph[dst].emplace_back(dst, src, cost); } int size() const { return graph.size(); } void clear() { graph.clear(); } void resize(int n) { graph.resize(n); } std::vector>& operator[](int v) { return graph[v]; } std::vector> operator[](int v) const { return graph[v]; } }; Graph<> graph; std::vector> chmexs; std::vector mexs, rmexs; int dfs(int v, int p) { auto& chmex = chmexs[v]; chmex.clear(); chmex.shrink_to_fit(); for (auto e : graph[v]) { int u = e.dst; if (u == p) continue; int m = dfs(u, v); while ((int)chmex.size() <= m) chmex.push_back(0); ++chmex[m]; } auto& mex = mexs[v]; mex = 0; while (mex < (int)chmex.size() && chmex[mex] > 0) ++mex; return mex; } void edfs(int v, int p, int pmex) { auto& chmex = chmexs[v]; if (pmex != -1) { while ((int)chmex.size() <= pmex) chmex.push_back(0); ++chmex[pmex]; } auto& mex = rmexs[v]; mex = 0; while (mex < (int)chmex.size() && chmex[mex] > 0) ++mex; for (auto e : graph[v]) { int u = e.dst; if (u == p) continue; int m = mexs[u]; int nmex = mex; if (m < nmex && chmex[m] == 1) nmex = m; edfs(u, v, nmex); } } void solve() { int n, m; std::cin >> n >> m; std::vector xs(m); for (auto& x : xs) { std::cin >> x; --x; } graph.resize(n); for (int i = 0; i < n - 1; ++i) { int u, v; std::cin >> u >> v; graph.span(true, --u, --v); } chmexs.resize(n); mexs.resize(n); rmexs.resize(n); dfs(0, -1); edfs(0, -1, -1); int grundy = 0; for (auto x : xs) grundy ^= rmexs[x]; if (grundy == 0) { std::cout << "-1 -1\n"; return; } std::terminate(); int ri = 0; while ((rmexs[xs[ri]] ^ grundy) >= rmexs[xs[ri]]) ++ri; int r = xs[ri]; dfs(r, -1); for (auto e : graph[r]) { int u = e.dst; if (mexs[u] == (rmexs[xs[ri]] ^ grundy)) { std::cout << ri + 1 << " " << u + 1 << "\n"; return; } } } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }