# HackerEarth Fredo's Crush problem solution

In this HackerEarth Fredo's Crush problem solution Fredo has crush on a girl in his class. He went to ask her out for a date. She, being a coder, gave her a simple graph with N vertices and M edges and asked him to solve a problem on the graph in order to go on a date with her.
The problem says:
Let there be some functions defined below:
For each vertex in the graph:
S = max (sum of all vertices lying in the maximum length simple path ending at that vertex)
That is, if there are two simple paths with length 3 ending at some vertex and there can be no simple path with length greater than 3, and P be the sum of vertices of first path and Q of second. So, S = max(P,Q).

Let A = minimum value of S[i] (1<=i<=n)
B = maximum value of S[i] (1<=i<=n)
You are given an equation Ax = By
Find the minimum value of x and y satisfying the equation.
Note: If there are no simple paths ending at some vertex, S for that vertex will be number of that vertex.
A simple path is a path in a graph which does not have repeating vertices.

## HackerEarth Fredo's Crush problem solution.

`#include<bits/stdc++.h>#define nmax 15using namespace std;int ans[nmax],sum[nmax];void find_hamiltonian_paths(int adj[nmax][nmax],int n){  bool dp[nmax][1<<nmax]={0};  int i,j,k;  for(i=0;i<n;i++)  {    dp[i][1<<i]=1;    ans[i]=0;sum[i]=i+1;  }  int limit=1<<n;  for(i=0;i<limit;i++)  {    int s=0;    int count=0,temp=i;                while(temp)                {      s+=log2(temp&-temp)+1;                        temp&=temp-1;                        count++;                }    for(j=0;j<n;j++)    {      if(i & (1<<j))      {        for(k=0;k<n;k++)          if(k!=j && adj[k][j] && (i & (1<<k))  && dp[k][i^(1<<j)])          {            dp[j][i]=1;            ans[j]=max(ans[j],count-1);                                          if(ans[j]==count-1)sum[j]=max(sum[j],s);            break;          }      }    }  }  /*for(i=0;i<n;i++)    printf("%d %d\n",ans[i],sum[i]);*/  //printf("\n");}int gcd(int a,int b){  return (b)?gcd(b,a%b):a;}int main(){  int t;  scanf("%d",&t);  while(t--)  {    int n,m,i,adj[nmax][nmax]={0};    scanf("%d%d",&n,&m);    for(i=0;i<m;i++)    {      int x,y;      scanf("%d%d",&x,&y);      adj[x-1][y-1]=adj[y-1][x-1]=1;    }    find_hamiltonian_paths(adj,n);    int minn,maxx;minn=maxx=sum[0];    for(i=1;i<n;i++)    {      if(minn>sum[i])minn=sum[i];      if(maxx<sum[i])maxx=sum[i];    }    int hcf=gcd(maxx,minn);    printf("%d %d\n",maxx/hcf,minn/hcf);  }  return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define mod 1000000007#define ll long long int#define pb push_back#define mk make_pairll power(ll a, ll b) {ll x = 1, y = a;    while(b > 0) {        if(b%2 == 1) {            x=(x*y);            if(x>mod) x%=mod;        }        y = (y*y);        if(y>mod) y%=mod;        b /= 2;    }    return x;}int adj[15][15],dist[15],path[15];int dp[15][1<<15];int n;pair<int,int> find(int x){  int i,s = 0;  int c = 0;  for(i = 0; i < n; i++) {    if(x & (1<<i)) {      s += i+1;      c++;    }  }  return make_pair(c,s);}void solve(int total){  pair<int,int>p = find(total);  p.first--;  int i,j;  for(i = 0; i < n; i++) {    if(total&(1<<i)) {      for(j = 0; j < n; j++) {        if(j != i && adj[i][j] != -1) {          if(dp[j][total&~(1<<i)] != -1) {            dp[i][total]++;            if(path[i] <= p.first) {              path[i] = p.first;              dist[i] = max(dist[i],p.second);            }            break;          }        }      }    }  }}int main() {  ios_base::sync_with_stdio(0); cin.tie(0);  int t,m,i,j,u,v;  cin>>t;  while(t--) {    cin>>n>>m;    memset(dp,-1,sizeof dp);    memset(adj,-1,sizeof adj);    while(m--) {      cin>>u>>v;      u--;      v--;      adj[u][v] = adj[v][u] = 1;    }    int maxi = INT_MIN;    int mini = INT_MAX;    for(i = 0; i < n; i++) {      dist[i] = i+1;      path[i] = 0;      dp[i][1<<i] = 1;    }    for(i = 0; i < (1<<n); i++) {      solve(i);    }    for(i = 0; i < n; i++ ) {      maxi = max(maxi,dist[i]);      mini = min(mini,dist[i]);    }    int lcm = maxi*mini/__gcd(maxi,mini);    cout<<lcm/mini<<" "<<lcm/maxi<<endl;  }  return 0;}`