# PROFESSOR MORIARITY Solutions BVPCSI06

Page Contents

### PROFESSOR MORIARITY Solutions BVPCSI06

A total twofold tree exists with n hubs and all the edges in this tree are undirected. Hubs are numbered from 1ton. Consider the root hub with the index1, and the parent of ith hub as floor (I/2).

Moriarity sees this tree and needs to make intricacies. He adds m extra undirected edges to the tree. Sherlock is delegated to check the quantity of Beautiful Paths in the subsequent diagram modulo 109+7.

A Beautiful Path is an exchanging succession of nearby hubs and undirected edges, which starts and finishes with hubs and doesn’t contain any hub more than once. Do take note of that a solitary hub is additionally viewed as a legitimate Beautiful way under this definition. It would be ideal if you allude to the models and notes underneath for occasions.

Info The main line of information contains two space-isolated numbers n and m — the quantity of hubs in the tree and the quantity of additional edges individually.

The accompanying m lines each contains two space-isolated numbers u and v — portraying an undirected additional edge whose endpoints are u and v.

Note that there might be different edges between hubs in the subsequent diagram.

Yield Yield one number — the quantity of excellent ways in the subsequent chart, modulo 109 + 7.

Imperatives

(1 ≤ n ≤ 109,0 ≤ m ≤ 4)

(1 ≤ u, v ≤ n,u ≠ v)

Test input

3 0

Test Output

Test input

3 1

2 3

Test Output

15

Test input

2 4

1 2

2 1

1 2

2 1

Test Output

12

Clarifications:

In the primary model the ways are: (1);(2);(3);(1, 2);(2, 1);(1, 3);(3, 1);(2, 1, 3);(3, 1, 2). (For clearness, the edges between hubs are precluded since there are no numerous edges for this situation.)

In the subsequent model, the ways are: (1);(1, 2);(1, 2, 3);(1, 3);(1, 3, 2); and likewise for ways beginning with 2and3. (5 × 3 = 15 ways altogether.)

In the third model, the ways are: (1);(2); any undirected edge associating the two hubs went in either bearing. (2 + 5 × 2 = 12 ways altogether.)

Solution

CODE C++14 :

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod=1000000007;
map<int,int>sz;
set<int>vis;
map<int,vector<int> >g;
int n,m,ans;

int get_sz(int t){
int ret=0;
for(int i=0;(t<<i)<=n;++i)
ret+=min(((t+1)<<i),n+1)-(t<<i);
return ret;
}
void ins_node(int x){for(;x;x/=2)sz[x]=0;}

void dfs(int x,int y){
vis.insert(x);
ans=(ans+(ll)y*sz[x])%mod;
for(int i:g[x])if(!vis.count(i))dfs(i,y);
vis.erase(x);
}

int main(){
ins_node(1);
for(cin>>n>>m;m –> 0;){
int x,y;cin>>x>>y;
g[x].push_back(y);g[y].push_back(x);
ins_node(x);ins_node(y);
}
for(auto i:sz){
int u=i.first,v=u/2;
int res=get_sz(u);sz[u]+=res;
if(v){sz[v]-=res;g[u].push_back(v);g[v].push_back(u);}
}
for(auto i:sz)dfs(i.first,i.second);
cout<<ans<<‘n’;
return 0;
}