#pragma region kyopro_template #define Nyaan_template #include #include #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define die(...) \ do { \ out(__VA_ARGS__); \ return; \ } while (0) using namespace std; using ll = long long; template using V = vector; using vi = vector; using vl = vector; using vvi = vector>; using vd = V; using vs = V; using vvl = vector>; using P = pair; using vp = vector

; using pii = pair; using vpi = vector>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } #ifdef NyaanDebug #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) template void _cout(const T &c) { cerr << c; } void _cout(const int &c) { if (c == 1001001001) cerr << "inf"; else if (c == -1001001001) cerr << "-inf"; else cerr << c; } void _cout(const unsigned int &c) { if (c == 1001001001) cerr << "inf"; else cerr << c; } void _cout(const long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else if (c == -1001001001 || c == -((1LL << 61) - 1)) cerr << "-inf"; else cerr << c; } void _cout(const unsigned long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else cerr << c; } template void _cout(const pair &p) { cerr << "{ "; _cout(p.fi); cerr << ", "; _cout(p.se); cerr << " } "; } template void _cout(const vector &v) { int s = v.size(); cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } "; } template void _cout(const vector> &v) { cerr << "[ "; for (const auto &x : v) { cerr << endl; _cout(x); cerr << ", "; } cerr << endl << " ] "; } void dbg_out() { cerr << endl; } template void dbg_out(const T &t, const U &... u) { _cout(t); if (sizeof...(u)) cerr << ", "; dbg_out(u...); } template void array_out(const T &v, int s) { cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } " << endl; } template void array_out(const T &v, int H, int W) { cerr << "[ "; for (int i = 0; i < H; i++) { cerr << (i ? ", " : ""); array_out(v[i], W); } cerr << " ] " << endl; } #else #define trc(...) #define trca(...) #define trcc(...) #endif inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template inline int getbit(T a, int i) { return (a >> i) & 1; } template inline void setbit(T &a, int i) { a |= (1LL << i); } template inline void delbit(T &a, int i) { a &= ~(1LL << i); } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template int btw(T a, T x, T b) { return a <= x && x < b; } template T ceil(T a, U b) { return (a + b - 1) / b; } constexpr long long TEN(int n) { long long ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template vector mkrui(const vector &v) { vector ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector mkiota(int N) { vector ret(N); iota(begin(ret), end(ret), 0); return ret; } template vector mkinv(vector &v) { vector inv(v.size()); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; void solve(); int main() { solve(); } #pragma endregion using namespace std; template struct BinaryTrie { using Container = int; struct Node { Node *nxt[2]; int exist; Node() {} }; Node *pool; int pid; T lazy; Node *nil; Node *root; BinaryTrie() : pid(0), lazy(T(0)), nil(nullptr) { pool = new Node[NODES]; nil = my_new(); nil->nxt[0] = nil->nxt[1] = root = nil; } Node *my_new(int exist_ = 0, int id = -1) { pool[pid].nxt[0] = pool[pid].nxt[1] = nil; pool[pid].exist = exist_; return &(pool[pid++]); } Node *merge(Node *l, Node *r) { pool[pid].nxt[0] = l; pool[pid].nxt[1] = r; pool[pid].exist = l->exist + r->exist; return &(pool[pid++]); } Node *add_(const T &x, int id, Node *n, int bit_idx = MAX_LOG) { if (bit_idx == -1) { if (n == nil) return my_new(1, id); n->exist++; return n; } else { if (((lazy >> bit_idx) & 1) == ((x >> bit_idx) & 1)) return merge(add_(x, id, n->nxt[0], bit_idx - 1), n->nxt[1]); else return merge(n->nxt[0], add_(x, id, n->nxt[1], bit_idx - 1)); } } public: void add(const T &x, int id = -1) { root = add_(x, id, root, MAX_LOG); } Node *del_(const T &x, int id, Node *n, int bit_idx = MAX_LOG) { if (bit_idx == -1) { n->exist--; return n; } else { if (((lazy >> bit_idx) & 1) == ((x >> bit_idx) & 1)) return merge(del_(x, id, n->nxt[0], bit_idx - 1), n->nxt[1]); else return merge(n->nxt[0], del_(x, id, n->nxt[1], bit_idx - 1)); } } public: void del(const T &x, int id = -1) { root = del_(x, id, root, MAX_LOG); } pair find_(const T &x, Node *n, int bit_idx = MAX_LOG) { if (bit_idx == -1) return pair(n->exist, 0); else { if (((lazy >> bit_idx) & 1) == ((x >> bit_idx) & 1)) return find_(x, n->nxt[0], bit_idx - 1); else return find_(x, n->nxt[1], bit_idx - 1); } } public: pair find(const T &x) { return find_(x, root, MAX_LOG); } private: pair max_element_(Node *n, int bit_idx = MAX_LOG) { if (bit_idx == -1) return pair(0,0); if (n->nxt[~(lazy >> bit_idx) & 1]->exist) { auto ret = max_element_(n->nxt[~(lazy >> bit_idx) & 1], bit_idx - 1); ret.first |= T(1) << bit_idx; return ret; } else { return max_element_(n->nxt[(lazy >> bit_idx) & 1], bit_idx - 1); } } public: pair max_element() { return max_element_(root, MAX_LOG); } private: pair min_element_(Node *n, int bit_idx = MAX_LOG) { if (bit_idx == -1) return pair(0, 0); if (n->nxt[(lazy >> bit_idx) & 1]->exist) { return min_element_(n->nxt[(lazy >> bit_idx) & 1], bit_idx - 1); } else { auto ret = min_element_(n->nxt[~(lazy >> bit_idx) & 1], bit_idx - 1); ret.first |= T(1) << bit_idx; return ret; } } public: pair min_element() { return min_element_(root, MAX_LOG); } private: pair get_kth_(Node *n, int64_t k, int bit_idx = MAX_LOG) { if (bit_idx == -1) return pair(0, 0); int ex0 = n->nxt[(lazy >> bit_idx) & 1]->exist; if (ex0 < k) { auto ret = get_kth_(n->nxt[~(lazy >> bit_idx) & 1], k - ex0, bit_idx - 1); ret.first |= T(1) << bit_idx; return ret; } else { return get_kth_(n->nxt[(lazy >> bit_idx) & 1], k, bit_idx - 1); } } public: T mex_query_(Node *n, int bit_index = MAX_LOG) { // distinct-values assert(lazy == 0); if (bit_index == -1 || n->nxt[0] == nil) return 0; if (n->nxt[0]->exist == (T(1) << bit_index)) { T ret = T(1) << bit_index; if (n->nxt[1]) ret |= mex_query_(n->nxt[1], bit_index - 1); return ret; } else { return mex_query_(n->nxt[0], bit_index - 1); } } public: pair get_kth(int64_t k) { return get_kth_(root, k, MAX_LOG); } void operate_xor(T x) { lazy ^= x; } }; /** * @brief Binary Trie * @docs docs/binary-trie.md */ using namespace std; template struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnweightedGraph = vector>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template WeightedGraph wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].eb(x, y, c); if (!is_directed) g[y].eb(y, x, c); } return g; } // Input of Edges template Edges esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) { Edges es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template vector> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector> d(N, vector(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } using namespace std; // Depth of Rooted Tree // unvisited nodes : d = -1 vector Depth(const UnweightedGraph &g, int start = 0) { vector d(g.size(), -1); auto dfs = [&](auto rec, int cur, int par = -1) -> void { d[cur] = par == -1 ? 0 : d[par] + 1; for (auto &dst : g[cur]) { if (dst == par) continue; rec(rec, dst, cur); } }; dfs(dfs, start); return d; } // Depth of Rooted Weighted Tree // unvisited nodes : d = -1 template vector Depth(const WeightedGraph &g, int start = 0) { vector d(g.size(), -1); auto dfs = [&](auto rec, int cur, T val, int par = -1) -> void { d[cur] = val; for (auto &dst : g[cur]) { if (dst == par) continue; rec(rec, dst, val + dst.cost, cur); } }; dfs(dfs, start, 0); return d; } // Diameter of Tree // return value : { {u, v}, length } pair, int> Diameter(const UnweightedGraph &g) { auto d = Depth(g, 0); int u = max_element(begin(d), end(d)) - begin(d); d = Depth(g, u); int v = max_element(begin(d), end(d)) - begin(d); return make_pair(make_pair(u, v), d[v]); } // Diameter of Weighted Tree // return value : { {u, v}, length } template pair, T> Diameter(const WeightedGraph &g) { auto d = Depth(g, 0); int u = max_element(begin(d), end(d)) - begin(d); d = Depth(g, u); int v = max_element(begin(d), end(d)) - begin(d); return make_pair(make_pair(u, v), d[v]); } // nodes on the path u-v ( O(N) ) template vector Path(G &g, int u, int v) { vi ret; int end = 0; auto dfs = [&](auto rec, int cur, int par = -1) -> void { ret.push_back(cur); if (cur == v) { end = 1; return; } for (int dst : g[cur]) { if (dst == par) continue; rec(rec, dst, cur); if (end) return; } if (end) return; ret.pop_back(); }; dfs(dfs, u); return ret; } using namespace std; template struct HeavyLightDecomposition { G& g; int idx; vector size, depth, in, out, nxt, par; HeavyLightDecomposition(G& g, int root = 0) : g(g), idx(0), size(g.size(), 0), depth(g.size(), 0), in(g.size(), -1), out(g.size(), -1), nxt(g.size(), root), par(g.size(), root) { dfs_sz(root); dfs_hld(root); } void build(int root) { dfs_sz(root); dfs_hld(root); } void dfs_sz(int cur) { size[cur] = 1; for (auto& dst : g[cur]) { if (dst == par[cur]) { if (g[cur].size() >= 2 && int(dst) == int(g[cur][0])) swap(g[cur][0], g[cur][1]); else continue; } depth[dst] = depth[cur] + 1; par[dst] = cur; dfs_sz(dst); size[cur] += size[dst]; if (size[dst] > size[g[cur][0]]) { swap(dst, g[cur][0]); } } } void dfs_hld(int cur) { in[cur] = idx++; for (auto dst : g[cur]) { if (dst == par[cur]) continue; nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst)); dfs_hld(dst); } out[cur] = idx; } template void edge_query(int u, int v, const F& f) { while (1) { if (in[u] > in[v]) swap(u, v); if (nxt[u] != nxt[v]) { f(in[nxt[v]], in[v] + 1); v = par[nxt[v]]; } else { if (u != v) f(in[u] + 1, in[v] + 1); break; } } } // TODO : verify template void uncommutable_edge_query(int u, int v, const F& f) { while (1) { if (nxt[u] != nxt[v]) { if (in[u] > in[v]) { f(in[u] + 1, in[nxt[u]], true); u = par[nxt[u]]; } else { f(in[nxt[v]], in[v] + 1, false); v = par[nxt[v]]; } } else { if (in[u] != in[v]) { if (in[u] > in[v]) f(in[u] + 1, in[v] + 1, true); else f(in[u] + 1, in[v] + 1, true); } break; } } } template void node_query(int u, int v, const F& f) { while (1) { if (in[u] > in[v]) swap(u, v); if (nxt[u] != nxt[v]) { f(in[nxt[v]], in[v] + 1); v = par[nxt[v]]; } else { f(in[u], in[v] + 1); break; } } } template void uncommutable_node_query(int u, int v, const F& f) { while (1) { if (nxt[u] != nxt[v]) { if (in[u] > in[v]) { f(in[u] + 1, in[nxt[u]], true); u = par[nxt[u]]; } else { f(in[nxt[v]], in[v] + 1, false); v = par[nxt[v]]; } } else { if (in[u] > in[v]) f(in[u] + 1, in[v], true); else f(in[u], in[v] + 1, true); break; } } } template void sub_edge_query(int u, const F& f) { f(in[u] + 1, out[u]); } template void sub_node_query(int u, const F& f) { f(in[u], out[u]); } int lca(int a, int b) { while (nxt[a] != nxt[b]) { if (in[a] < in[b]) swap(a, b); a = par[nxt[a]]; } return depth[a] < depth[b] ? a : b; } }; void solve() { ini(N, M); vl a(M); in(a); each(x, a) x--; auto g = graph(N); auto dep = Depth(g); // HeavyLightDecomposition hld(g); BinaryTrie trie; vi sub(N); { auto dfs = [&](auto rec, int cur, int par = -1) -> int { auto root = trie.nil; each(dst, g[cur]) { if (dst == par) continue; int val = rec(rec, dst, cur); if (trie.find_(val, root).first == 0) root = trie.add_(val, -1, root); } sub[cur] = trie.mex_query_(root); return sub[cur]; }; dfs(dfs, 0); } trc(sub); // HeavyLightDecomposition hld(g); trie.pid = 1; vi ans(N); { auto dfs = [&](auto rec, int cur, int pval, int par = -1) -> void { auto root = trie.nil; unordered_map m; root = trie.add_(pval, -1, root); m[pval]++; each(dst, g[cur]) { if (dst == par) continue; if (m[sub[dst]] == 0) root = trie.add_(sub[dst], -1, root); m[sub[dst]]++; } ans[cur] = trie.mex_query_(root, 18); each(dst, g[cur]) { if (dst == par) continue; if (m[sub[dst]] == 1) root = trie.del_(sub[dst], -1, root); rec(rec, dst, trie.mex_query_(root), cur); if (m[sub[dst]] == 1) root = trie.add_(sub[dst], -1, root); } }; dfs(dfs, 0, (1 << 18) - 1); } trc(ans); int xor_ = 0; each(x, a) xor_ ^= ans[x]; if (xor_ == 0) { die(-1, -1); } set cnt; each(x, a) cnt.insert(x); each(cur, cnt) { int p = -1; each(dst, g[cur]) { if (dep[dst] < dep[cur]) { p = dst; continue; } if ((ans[cur] ^ sub[dst] ^ xor_) == 0) { // これが答え int i = -1; rep(_, M) if (a[_] == cur) i = _; out(i + 1, dst + 1); return; } } if (p != -1 and (ans[cur] ^ xor_) < ans[cur]){ int i = -1; rep(_, M) if (a[_] == cur) i = _; die(i + 1, p + 1); } } exit(1); }