/*
I find it wholesome to be alone the greater part of the time.
To be in company, even with the best, is soon wearisome and dissipating.
I love to be alone.
I never found the companion that was so companionable as solitude.
*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 1;
const int Mod = 1e9 + 7;
//const int inf =
int n, m;
int lift[maxN][20];
int depth[maxN];
int dp[maxN];
struct TDSU{
vector <int> lab;
TDSU(){}
TDSU(int _n){
lab.resize(_n, -1);
}
inline void resize(int _n){
lab.resize(_n, -1);
}
inline int find_set(int u){
if (lab[u] < 0) return u;
return lab[u] = find_set(lab[u]);
}
inline void unite(int u, int v){
u = find_set(u);
v = find_set(v);
if (u == v) return;
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
}
};
TDSU dsu;
vector <int> adj[maxN];
void pre_dfs(int u, int p){
lift[u][0] = p;
for (int i = 1; i < 20; ++i){
lift[u][i] = lift[lift[u][i - 1]][i - 1];
}
depth[u] = depth[p] + 1;
for (int i: adj[u]){
if (i == p) continue;
pre_dfs(i, u);
}
}
inline int lca(int u, int v){
if (depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
while (k){
int t = __builtin_ctz(k);
u = lift[u][t];
k -= 1 << t;
}
if (u == v) return u;
for (int i = 19; i >= 0; --i){
if (lift[u][i] != lift[v][i]){
u = lift[u][i];
v = lift[v][i];
}
}
return lift[u][0];
}
void dfs(int u, int p){
for (int i: adj[u]){
if (i == p) continue;
dfs(i, u);
dp[u] += dp[i];
}
if (dp[u]){
dsu.unite(u, p);
dsu.unite(u + n, p + n);
}
}
void Init(){
cin >> n >> m;
dsu.resize(2 * n + 1);
for (int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
pre_dfs(1, 0);
for (int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
int p = lca(u, v);
++dp[u];
++dp[v];
dp[p] -= 2;
if (p == u || p == v) continue;
dsu.unite(u + n, v);
dsu.unite(u, v + n);
}
dfs(1, 0);
for (int i = 1; i <= n; ++i){
if (dsu.find_set(i) == dsu.find_set(i + n)){
cout << 0;
exit(0);
}
}
map <int, bool> mp;
ll ans = 1;
for (int i = 1; i <= n; ++i){
if (!mp[dsu.find_set(i)]){
mp[dsu.find_set(i)] = 1;
ans <<= 1;
if (ans > Mod) ans -= Mod;
}
}
cout << ans;
}
#define debug
#define taskname "test"
signed main(){
faster
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
int tt = 1;
//cin >> tt;
while (tt--){
Init();
}
if (fopen("timeout.txt", "r")){
ofstream timeout("timeout.txt");
timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
timeout.close();
#ifndef debug
cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
#endif // debug
}
}
Compilation message
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
usmjeri.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
26672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
16596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
25752 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
25644 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
25936 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
48 ms |
25784 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
