#include "bits/stdc++.h" using namespace std; #define int long long #define REP(i, n) for (int i = 0; i < (int)n; ++i) #define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i) #define FOR(i, s, n) for (int i = s; i < (int)n; ++i) #define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i) #define ALL(a) a.begin(), a.end() #define IN(a, x, b) (a <= x && x < b) templateistream&operator >>(istream&is,vector&vec){for(T&x:vec)is>>x;return is;} templateinline void out(T t){cout << t << "\n";} templateinline void out(T t,Ts... ts){cout << t << " ";out(ts...);} templateinline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;} templateinline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;} constexpr int INF = 1e18; template class ReRooting { public: int NodeCount; std::vector> Adjacents; std::vector> IndexForAdjacent; std::vector Res; std::vector> DP; T Identity; std::function Operate; std::function OperateNode; public: ReRooting(int nodeCount, std::vector> edges, T identity, std::function operate, std::function operateNode) { NodeCount = nodeCount; Identity = identity; Operate = operate; OperateNode = operateNode; std::vector> adjacents(nodeCount); std::vector> indexForAdjacents(nodeCount); for (int i = 0; i < edges.size(); i++) { auto &edge = edges[i]; indexForAdjacents[edge[0]].push_back(adjacents[edge[1]].size()); indexForAdjacents[edge[1]].push_back(adjacents[edge[0]].size()); adjacents[edge[0]].push_back(edge[1]); adjacents[edge[1]].push_back(edge[0]); } Adjacents = std::vector>(nodeCount); IndexForAdjacent = std::vector>(nodeCount); for (int i = 0; i < nodeCount; i++) { Adjacents[i] = adjacents[i]; IndexForAdjacent[i] = indexForAdjacents[i]; } DP = std::vector>(Adjacents.size()); Res = std::vector(Adjacents.size()); for (int i = 0; i < Adjacents.size(); i++) DP[i] = std::vector(Adjacents[i].size()); if (NodeCount > 1) Initialize(); else if (NodeCount == 1) Res[0] = OperateNode(Identity, 0); } T Query(int node) { return Res[node]; } private: void Initialize() { std::vector parents(NodeCount); std::vector order(NodeCount); #pragma region InitOrderedTree int index = 0; std::stack stack; stack.push(0); parents[0] = -1; while (stack.size() > 0) { auto node = stack.top(); stack.pop(); order[index++] = node; for (int i = 0; i < Adjacents[node].size(); i++) { auto adjacent = Adjacents[node][i]; if (adjacent == parents[node]) continue; stack.push(adjacent); parents[adjacent] = node; } } #pragma endregion #pragma region fromLeaf for (int i = order.size() - 1; i >= 1; i--) { auto node = order[i]; auto parent = parents[node]; T accum = Identity; int parentIndex = -1; for (int j = 0; j < Adjacents[node].size(); j++) { if (Adjacents[node][j] == parent) { parentIndex = j; continue; } accum = Operate(accum, DP[node][j]); } DP[parent][IndexForAdjacent[node][parentIndex]] = OperateNode(accum, node); } #pragma endregion #pragma region toLeaf for (int i = 0; i < order.size(); i++) { auto node = order[i]; T accum = Identity; std::vector accumsFromTail(Adjacents[node].size()); accumsFromTail[accumsFromTail.size() - 1] = Identity; for (int j = accumsFromTail.size() - 1; j >= 1; j--) accumsFromTail[j - 1] = Operate(DP[node][j], accumsFromTail[j]); for (int j = 0; j < accumsFromTail.size(); j++) { DP[Adjacents[node][j]][IndexForAdjacent[node][j]] = OperateNode(Operate(accum, accumsFromTail[j]), node); accum = Operate(accum, DP[node][j]); } Res[node] = OperateNode(accum, node); } #pragma endregion } }; signed main(){ int N, M; cin >> N >> M; vectora(M); REP(i, M) { cin >> a[i]; --a[i]; } vector>g; vector>edges(N); REP(i, N - 1) { int a, b; cin >> a >> b; --a; --b; g.push_back({a, b}); edges[a].emplace_back(b); edges[b].emplace_back(a); } auto merge = [](int a, int b) -> int { return a | b; }; auto f = [](int a, int b) -> int { REP(i, 20) { if(!(a & (1ll << i))) return 1ll << i; } return 0; }; ReRooting rr(N, g, 0ll, merge, f); int XOR = 0; vectorgrundy(N); REP(i, N) { int state = rr.Query(i); REP(j, 20) { if(state & (1ll << j)) grundy[i] = j; } } REP(i, M) { XOR ^= grundy[a[i]]; } vectorcnt(N, -1); REP(i, M) cnt[a[i]] = i; if(XOR) { REP(i, N) { if(cnt[i] == -1) continue; REP(j, rr.Adjacents[i].size()) { int x = rr.DP[i][j]; REP(k, 20) { if(x & (1ll << k)) { x = k; break; } } int next_XOR = XOR ^ grundy[i] ^ x; if(next_XOR == 0) { out(cnt[i] + 1, rr.Adjacents[i][j] + 1); return 0; } } } } else { out(-1, -1); } }