# HackerEarth Strange Road System problem solution

In this HackerEarth Strange Road System problem solution, Marichka will visit HackerLand, the country with N (1 <= N <= 10^5) cities, on her spring holidays. She feels very excited because of this.

During the next Q days one of the two following events happens.

- 1 U V P (1 <= U <= N, 1 <= V <= N, 1 <= P <= 10^9) --- hackers build a new bidirectional road with happiness points \$P\$ between cities U and V

- 2 U V (1 <= U <= N, 1 <= V <= N) --- Your task is to answer the query. You are given cities numbers --- U and V, and your task is to find maximum happiness Marichka can get after travelling in some way(maybe through some intermediate cities) between cities U and V. If there is no way to get from the city U to the city V between them, then simply output -1.

If Marichka's happiness before traversing some road was X and road's happiness points are Y, then after traversing it Marichka's happiness will be equal to X xor Y.  Marichka can traverse one road many times. She also can visit some city many times during her travel.

Initially, there are no roads in HackerLand.

## HackerEarth Strange Road System problem solution.

`#include <bits/stdc++.h>using namespace std;#define pb push_backint n , m;int p; //Parent array for DSUint d; //Distance from the root in DSUvector<int> b; //Linear basises for connected componentsvoid add(int x , vector<int> &b) //Function to add x in linear basis{    for(int i = 0; i < b.size(); i++)     {        int t= b[i];         if((x ^ t) < x)         {            x ^= t;        }    }    if(x == 0)        return;    for(int i = 0; i < b.size(); i++)    {        if((x ^ b[i]) < b[i])            b[i] ^= x;    }    b.pb(x); //Add x to linear basis    sort(b.begin() , b.end() , greater<int>());}int mx(int x , vector<int> &b){    for(int i = 0; i < b.size(); i++)    {        int t = b[i];        if((x ^ t) > x)        {            x ^= t;        }    }    return x;}int find(int u){    if(u == p[u])        return u;    int P = p[u];     int root = find(P);         d[u] ^= d[P];     p[u] = root;     return root; }void init(int n) {    for(int i = 0; i < n; i++)    {        p[i] = i;        b[i].clear();        d[i] = 0;    }}void merge(int u , int v , int w) //Function to merge two vertices in DSU{    int pu = find(u) , pv = find(v);    if(pu == pv) //If they are in the same set     {        add(w ^ d[u] ^ d[v] , b[pu]);         return;    }    p[pv] = pu;     d[pv] = d[v] ^ d[u] ^ w;    for(auto x : b[pv])    {        add(x , b[pu]); //Merging U-basis and V-basis    }}int main(){    ios_base::sync_with_stdio(0);            int n;    assert(cin >> n);        assert(1 <= n && n <= 100000);    init(n);    int q;    cin >> q;        assert(1 <= q && q <= 100000);    while(q--)    {        int type;        assert(cin >> type);        assert(1 <= type && type <= 2);        if(type == 1)        {            int u , v , w;            assert(cin >> u >> v >> w);            assert(1 <= u && u <= n);            assert(1 <= v && v <= n);            assert(1 <= w && w <= 1e9);            u--;v--;            merge(u , v , w);        }        else        {            int u , v;            assert(cin >> u >> v);            assert(1 <= u && u <= n);            assert(1 <= v && v <= n);            u--;v--;            if(find(u) != find(v))            {                cout << -1 << endl;                continue;            }            //cout << d[u] << " " << d[v] << endl;                        cout << mx(d[u] ^ d[v] , b[find(u)]) << endl;        }    }}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define pb push_backint n , m;int p; //Parent array for DSUint d; //Distance from the root in DSUvector<int> b; //Linear basises for connected componentsvoid add(int x , vector<int> &b) //Function to add x in linear basis{    for(int i = 0; i < b.size(); i++) // Iterating through all integers in basis to combine x with some elements of linear basis.    //As the result x should have minimum possible value    {        int t= b[i];         if((x ^ t) < x)         {            x ^= t;        }    }    if(x == 0) //If x is equal to zero, there is no need to add x to linear basis        return;    for(int i = 0; i < b.size(); i++) //If can make some elements of linear basis smaller, we should do this    {        if((x ^ b[i]) < b[i])            b[i] ^= x;    }    b.pb(x); //Add x to linear basis    sort(b.begin() , b.end() , greater<int>());}int mx(int x , vector<int> &b){    for(int i = 0; i < b.size(); i++)    {        int t = b[i];        if((x ^ t) > x)        {            x ^= t;        }    }    return x;}int find(int u){    if(u == p[u])        return u;    int P = p[u];     int root = find(P);        d[u] ^= d[P]; //Keeping d up-to-date    p[u] = root; //And p    return root; }void init(int n) // A standart function to initialize DSU{    for(int i = 0; i < n; i++)    {        p[i] = i;        b[i].clear();        d[i] = 0;    }}void merge(int u , int v , int w){    int pu = find(u) , pv = find(v);    if(pu == pv) //If they are in the same set     {        add(w ^ d[u] ^ d[v] , b[pu]);         return;    }    p[pv] = pu;     d[pv] = d[v] ^ d[u] ^ w;     for(auto x : b[pv])    {        add(x , b[pu]); //Merging U-basis and V-basis    }}int main(){    ios_base::sync_with_stdio(0);            int n;    assert(cin >> n);        assert(1 <= n && n <= 100000);    init(n);    int q;    cin >> q;        assert(1 <= q && q <= 100000);    while(q--)    {        int type;        assert(cin >> type);        assert(1 <= type && type <= 2);        if(type == 1)        {            int u , v , w;            assert(cin >> u >> v >> w);            assert(1 <= u && u <= n);            assert(1 <= v && v <= n);            assert(1 <= w && w <= 1e9);            u--;v--;            merge(u , v , w);        }        else        {            int u , v;            assert(cin >> u >> v);            assert(1 <= u && u <= n);            assert(1 <= v && v <= n);            u--;v--;            if(find(u) != find(v))            {                cout << -1 << endl;                continue;            }                        cout << mx(d[u] ^ d[v] , b[find(u)]) << endl;        }    }}`