#define _USE_MATH_DEFINES
#include <immintrin.h>
#include <math.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <chrono>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
namespace std {
template<typename Fun>
struct y_combinator {
const Fun fun;
explicit y_combinator(const Fun&& fun) : fun(std::forward<const Fun>(fun)) {}
template<typename... Args>
auto operator()(Args&&... args) const {
return fun(std::ref(*this), std::forward<Args>(args)...);
}
};
template <typename T> void mineq(T& element, const T value) {
element = std::min<T>(element, value);
}
template <typename T> void maxeq(T& element, const T value) {
element = std::max<T>(element, value);
}
} // namespace std
#define INF ((int)1e9 + 1329)
#define INF_LL ((int64_t)1e18)
#define filin(x) freopen(x, "r", stdin)
#define filout(x) freopen(x, "w", stdout)
typedef int64_t ll;
typedef uint64_t ul;
typedef long double ld;
//const ld PI = acos(-1.0);
#ifndef __APPLE__
mt19937 rnd((uint32_t)time(0));
#else
mt19937 rnd(57);
#endif
struct Solution {
signed operator()() {
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; ++i) {
int a, b; cin >> a >> b;
a--; b--;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
constexpr int lg = 22;
vector<int> pae(n, -1), hst(n - 1);
array<vector<int>, lg> bp;
vector<int> dep(n);
bp.fill(vector<int>(n, -1));
auto dfs = y_combinator([&](auto dfs, int v = 0, int p = -1, int d = 0, int pe = -1) -> void {
if (pe != -1)
hst[pe] = p;
pae[v] = pe;
dep[v] = d;
bp[0][v] = p;
for (auto& it : g[v])
if (it.first != p)
dfs(it.first, v, d + 1, it.second);
});
dfs();
for (int l = 1; l < lg; ++l)
for (int i = 0; i < n; ++i)
bp[l][i] = (bp[l - 1][i] == -1 ? -1 : bp[l - 1][bp[l - 1][i]]);
auto la = [&](int v, int d) -> int {
for (int l = 0; l < lg; ++l)
if ((d >> l) & 1)
v = bp[l][v];
return v;
};
auto lca = [&](int a, int b) -> int {
if (dep[a] < dep[b])
swap(a, b);
a = la(a, dep[a] - dep[b]);
if (a == b)
return a;
for (int l = lg - 1; l >= 0; --l) {
if (bp[l][a] != bp[l][b]) {
a = bp[l][a];
b = bp[l][b];
}
}
return bp[0][a];
};
struct DSU {
vector<int> dt, sz;
vector<int> &mx, &dep;
int comp;
DSU(int n, vector<int>& mx, vector<int>& dep) : mx(mx), dep(dep) {
int ps = (int)mx.size();
for (int i = 0; i < ps; ++i)
mx.push_back(mx[i]);
comp = n;
dt.resize(n);
iota(dt.begin(), dt.end(), 0);
sz.resize(n, 1);
}
int get(int v) {
return (dt[v] == v ? v : dt[v] = get(dt[v]));
}
void unite(int a, int b) {
a = get(a);
b = get(b);
if (a == b)
return;
comp--;
if (sz[a] < sz[b])
swap(a, b);
dt[b] = a;
sz[a] += sz[b];
mx[a] = (dep[mx[a]] < dep[mx[b]] ? mx[a] : mx[b]);
}
} d((n - 1) * 2, hst, dep);
auto neg = [&](int v) -> int {
if (v >= n - 1)
return v - (n - 1);
return v + (n - 1);
};
while (m--) {
int a, b; cin >> a >> b;
a--; b--;
int lc = lca(a, b);
int tgd = dep[lc];
int ora = a, orb = b;
int v = pae[a];
if (a != 0)
a = hst[pae[a]];
while (a > 0 && dep[a] > tgd) {
d.unite(v, pae[a]);
d.unite(neg(v), neg(pae[a]));
a = d.mx[d.get(v)];
}
v = pae[b];
if (b != 0)
b = hst[pae[b]];
while (b > 0 && dep[b] > tgd) {
d.unite(v, pae[b]);
d.unite(neg(v), neg(pae[b]));
b = d.mx[d.get(v)];
}
a = ora;
b = orb;
if (tgd != dep[a] && tgd != dep[b]) {
d.unite(pae[a], neg(pae[b]));
d.unite(neg(pae[a]), pae[b]);
}
// for (auto& it : d.dt)
// cout << it << " ";
// cout << "\n";
}
for (int i = 0; i < n - 1; ++i) {
if (d.get(i) == d.get(neg(i))) {
cout << "0\n";
return 0;
}
}
ll res = 1ll;
constexpr ll mod = 1e9 + 7;
assert(d.comp % 2 == 0);
d.comp /= 2;
while (d.comp--) {
res *= 2;
res %= mod;
}
cout << res << "\n";
return 0;
}
Solution() {}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) {
int exit_code = Solution()();
if (exit_code)
exit(exit_code);
// cout << "\n";
}
return 0;
}
//3 1
//1 2
//1 3
//2 3
//4 1
//1 2
//2 3
//3 4
//2 4
//
//7 2
//1 2
//1 3
//4 2
//2 5
//6 5
//5 7
//1 7
//2 6
//
//4 3
//1 2
//1 3
//1 4
//2 3
//2 4
//3 4
//WA test 1. Contents:
//6 2
//1 2
//2 3
//3 4
//4 5
//5 6
//5 4
//2 1
//
//Correct:
//32
//Clever:
//16
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
22632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
65208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1372 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
57776 KB |
Output is correct |
| 2 |
Correct |
281 ms |
57780 KB |
Output is correct |
| 3 |
Correct |
178 ms |
37940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
57836 KB |
Output is correct |
| 2 |
Correct |
317 ms |
57840 KB |
Output is correct |
| 3 |
Incorrect |
191 ms |
38704 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
281 ms |
57968 KB |
Output is correct |
| 2 |
Correct |
220 ms |
57640 KB |
Output is correct |
| 3 |
Correct |
182 ms |
38704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
58276 KB |
Output is correct |
| 2 |
Correct |
245 ms |
57904 KB |
Output is correct |
| 3 |
Correct |
143 ms |
37856 KB |
Output is correct |
