# HackerEarth Edges on a path problem solution

In this HackerEarth Edges on a path problem solution Given a connected graph with n nodes and m edges, where m <= n.You are also given two nodes a and b of the graph.
You need to find the number of edges which are present in all paths between a and b.

## HackerEarth Edges on a path problem solution.

`#include <algorithm>#include <bitset>#include <cassert>#include <chrono>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <limits>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <ratio>#include <set>#include <sstream>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#include <climits>#define ll long long#define ld long double#define mp make_pair#define pb push_back#define in insert#define vll vector<ll>#define endl "\n"#define pll pair<ll,ll>#define f first#define s second#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)#define int ll#define sz(x) (ll)x.size()#define all(x) (x.begin(),x.end())using namespace std; const ll INF = 1e12;const ll N =(1e5+5); // TODO : change value as per problemconst ll M = (3e5+5);const ll MOD = 1e9+7;vll graph[N];int U[M],V[M];//edge list representation of input graphvll tree[N];//Bridge Tree formed from the given graphbool isbridge[M]; // if i'th edge is a bridge edge or not int vis[N],arr[N],T,cmpno;//supporting stuffqueue<int> Q[N];int nice[N];int adj(int u,int e){  return U[e]==u?V[e]:U[e];}int dfs0(int u,int edge)//mark bridges{   int dbe = arr[u] = T++;  vis[u]=1;  for(int i=0;i<graph[u].size();i++)  {    int e = graph[u][i];    int w = adj(u,e);    if(!vis[w])      dbe = min(dbe,dfs0(w,e));    else if(e!=edge)      dbe = min(dbe,arr[w]);  }  if(dbe == arr[u] && edge!=-1)    isbridge[edge]=true;  return dbe;}void dfs1(int v)  //Builds the tree with each edge a bridge from original graph{  int currcmp = cmpno; // current component no.  Q[currcmp].push(v);// A different queue for each component, coz during bfs we shall go to another component (step of dfs) and then come   back to this one and continue our bfs  vis[v]=1;  nice[v] = currcmp;  while(!Q[currcmp].empty()) //bfs. Exploring all nodes of this  component  {       int u = Q[currcmp].front();    Q[currcmp].pop();        for(int i=0;i<graph[u].size();i++)    {      int e = graph[u][i];      int w = adj(u,e);      if(vis[w])continue;      nice[w] = currcmp;      if(isbridge[e])   //if the edge under consideration is bridge and other side is not yet explored, go there (step of dfs)      {        cmpno++;        tree[currcmp].push_back(cmpno);        tree[cmpno].push_back(currcmp);        dfs1(w);      }      else  //else continue with our bfs      {        Q[currcmp].push(w);        vis[w]=1;      }    }  }}void solve(){  int n,m;  cin >> n >> m;  int a,b;  cin >> a >> b;  a--;  b--;  for(int i= 0;i<m;i++){    int u,v;    cin >> u >> v;    u--;    v--;    U[i] = v;    V[i] = u;    graph[u].pb(i);    graph[v].pb(i);  }  dfs0(0,-1);   memset(vis,0,sizeof(vis));   dfs1(0);      int u = nice[a];   int v = nice[b];   queue<int> q;   vector<int> dis(cmpno+1,-1);   dis[u] =0;   q.push(u);   while(!q.empty()){    int p = q.front();    q.pop();    for(auto g:tree[p]){      if(dis[g] == -1){        dis[g] =  dis[p] + 1;        q.push(g);      }    }   }   cout << dis[v] << endl;}signed main(){     ios_base::sync_with_stdio(0);    cin.tie(NULL);     // freopen(".in","r",stdin);freopen(".out","w",stdout);         ll tt=1;        // cin >> tt;    while(tt--){            solve();    }    }`

### Second solution

`#include <bits/stdc++.h>#define X first#define Y secondusing namespace std;template <class T, class L> inline bool smax(T &x, L y){  return x < y ? ( x = y, 1) : 0;  }template <class T, class L> inline bool smin(T &x, L y){  return y < x ? ( x = y, 1) : 0;  }typedef pair <int, int> pii;typedef long long ll;const int maxn = 1e5 + 17, lg = 17, mod = 1e9 + 7;int n, m, q, edge[maxn], comp[maxn], h[maxn], gp, cnt[maxn], po[maxn], par[maxn][lg];bool bl[maxn], seen[maxn], is[maxn];vector<int> g[maxn];pii e[maxn];int hi(int v = 0, int p = -1){    int ret = h[v];    seen[v] = 1;    for(auto i : g[v]){    int u = edge[i] ^ v;    if(!seen[u]){        h[u] = h[v] + 1;        int t = hi(u, v);        if(t == h[u])  bl[i] = 1;        smin(ret, t);    }    else if(u != p)  smin(ret, h[u]);    }    return ret;}void hello(int v){    cnt[ comp[v] = gp ]++;    for(auto i : g[v]){    int u = edge[i] ^ v;    if(!bl[i] && comp[u] == -1)        hello(u);    }}void dfs(int v = 0){    for(int i = 1; i < lg; i++)  par[v][i] = par[ par[v][i - 1] ][i - 1];    for(auto u : g[v])    if(u != par[v][0]){        h[u] = h[v] + 1, par[u][0] = v;        cnt[u] += cnt[v];        dfs(u);    }}int lca(int v, int u){    if(h[v] > h[u])  swap(v, u);    for(int i = 0; i < lg; i++)    if(h[u] - h[v] >> i & 1)        u = par[u][i];    for(int i = lg - 1; i >= 0; i--)    if(par[v][i] != par[u][i])        v = par[v][i], u = par[u][i];    return v == u ? v : par[v][0];}void build_tree(){    fill(g, g + n, vector<int>());    for(int i = 0; i < m; i++)    if(bl[i])        g[ comp[ e[i].X ] ].push_back(comp[ e[i].Y ]),        g[ comp[ e[i].Y ] ].push_back(comp[ e[i].X ]);    dfs();}int main(){    ios::sync_with_stdio(0), cin.tie(0);    for(int i = po[0] = 1; i < maxn; i++)  po[i] = (po[i - 1] << 1) % mod;    cin >> n >> m;    int a, b;    cin >> a >> b;    a--, b--;    for(int i = 0, v, u; i < m; i++){    cin >> v >> u, v--, u--;    edge[i] = v ^ u, e[i] = {v, u};    g[v].push_back(i), g[u].push_back(i);    }    hi();    memset(comp, -1, sizeof comp);    for(int i = 0; i < n; i++)    if(comp[i] == -1){        hello(i);        cnt[gp] = is[gp] = cnt[gp] - 1;        gp++;    }    build_tree();    cout << h[comp[a]] + h[comp[b]] - 2 * h[lca(comp[a], comp[b])] << '\n';    return 0;    cin >> q;    for(int v, u; q--; ){    cin >> v >> u, v--, u--;    v = comp[v], u = comp[u];    int p = lca(v, u);    cout << po[ cnt[v] + cnt[u] - 2 * cnt[p] + is[p] ] << '\n';    }    return 0;}`