#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> pth[300100];
int p[20][300100];
int dep[300100];
int grp[300100];
int ref[300100];
int col[300100];
vector<int> ppp[300100];
void dfs(int par, int idx,int d) {
p[0][idx]=par;
dep[idx]=d;
for (auto i:pth[idx]) {
if (i==par) continue;
dfs(idx,i,d+1);
}
}
struct lcaInfo {
int a,b,lca,sz;
};
struct path{
int a,b;
lcaInfo l;
};
bool operator< (const path &a, const path &b) {
if (dep[a.l.lca]!=dep[b.l.lca]) return dep[a.l.lca]<dep[b.l.lca];
return a.l.sz>a.l.sz;
}
lcaInfo lca(int a,int b) {
if (dep[a]<dep[b]) swap(a,b);
//printf("asdd %d %d\n",dep[a],dep[b]);
int tmp;
for (int i=19;i>=0;i--) {
if (dep[p[i][a]]>dep[b]) {
//if (dep[p[i][a]]>dep[b]) cur=a;
a=p[i][a];
}
}
//printf("asdd %d %d %d %d\n",dep[a],dep[b],a,b);
tmp=a;
if (dep[a]!=dep[b]) a=p[0][a];
if (a==b) return lcaInfo{tmp,0,a,1};
//printf("asd %d %d\n",a,b);
for (int i=19;i>=0;i--) {
if (p[i][a]!=p[i][b]) {
a=p[i][a];
b=p[i][b];
}
}
return lcaInfo{a,b,p[0][a],2};
}
bool chk[600100];
void ddd(int idx,int c) {
col[idx]=c;
for (auto a:ppp[idx]) {
if (col[a]==c) {
printf("0\n");
exit(0);
} else if (col[a]!=0) {
continue;
}
ddd(a,(c==1)?2:1);
}
}
int mod = 1000000007;
int poww(int xx) {
if (xx==0) return 1;
if (xx==1) return 2;
long long m = poww(xx/2);
m=m*m;
m%=mod;
if (xx%2) return (2*m)%mod;
return m;
}
int main () {
int n,m;
scanf("%d%d",&n,&m);
int a,b;
for (int i=1;i<n;i++) {
scanf("%d%d",&a,&b);
pth[a].push_back(b);
pth[b].push_back(a);
}
dfs(1,1,1);
for (int i=1;i<20;i++) {
for (int j=1;j<=n;j++) {
p[i][j]=p[i-1][p[i-1][j]];
}
}
vector<path> qq;
for (int i=0;i<m;i++) {
scanf("%d%d",&a,&b);
qq.push_back(path{a,b,lca(a,b)});
//printf("%d %d %d %d %d\n",qq.back().a,qq.back().b,qq.back().l.a,qq.back().l.b,qq.back().l.lca);
}
sort(qq.begin(),qq.end());
for (int i=1;i<=n;i++) {
grp[i]=i;
}
int curGrp=n+1;
int xx,rr,rrr;
int cura,curb;
for (auto &i:qq) {
//printf("%d %d %d\n",i.a,i.b,i.l.lca);
if (i.l.sz==1) {
//printf("yy\n");
if (grp[i.l.a]>n) {
xx=grp[i.l.a];
rr=ref[i.l.a];
} else {
xx=curGrp++;
rr=i.l.a;
}
//printf("--%d %d\n",xx,rr);
cura=(i.a==i.l.lca)?i.b:i.a;
while (cura!=i.l.lca&&grp[cura]<=n) {
grp[cura]=xx;
ref[cura]=rr;
cura=p[0][cura];
}
} else {
xx=-1;
//printf("--- %d %d\n",i.l.a,i.l.b);
if (grp[i.l.a]>n) {
xx=grp[i.l.a];
rr=ref[i.l.a];
} else {
rr=i.l.a;
}
if (grp[i.l.b]>n) {
xx=grp[i.l.b];
rrr=ref[i.l.b];
} else {
rrr=ref[i.l.b];
}
if (xx==-1) xx=curGrp++;
//printf("+++ %d\n",xx);
cura=i.a;
curb=i.b;
while (cura!=i.l.lca&&grp[cura]<=n) {
grp[cura]=xx;
ref[cura]=rr;
//printf("-- %d %d\n",cura,xx);
cura=p[0][cura];
}
while (curb!=i.l.lca&&grp[cura]<=n) {
grp[curb]=xx;
ref[curb]=rrr;
//printf("-- %d %d\n",curb,xx);
curb=p[0][curb];
}
if (rr==rrr) {
printf("0\n");
return 0;
}
ppp[rrr].push_back(rr);
ppp[rr].push_back(rrr);
}
}
for (int i=1;i<=n;i++) {
if (col[i]==0) {
ddd(i,1);
}
}
int cnt=0;
for (int i=2;i<=n;i++) {
if (!chk[grp[i]]) {
chk[grp[i]]=true;
cnt++;
}
printf("- %d %d\n",i,grp[i]);
}
printf("%d\n",poww(cnt));
return 0;
}
Compilation message
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:98:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
usmjeri.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
^
usmjeri.cpp:113:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
41180 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
435 ms |
87592 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
87592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
87592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
87592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
87592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
667 ms |
87592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
643 ms |
95132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
625 ms |
102740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
618 ms |
111056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
