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_back
int n , m;
int p[100005]; //Parent array for DSU
int d[100005]; //Distance from the root in DSU
vector<int> b[100005]; //Linear basises for connected components
void 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_back
int n , m;
int p[100005]; //Parent array for DSU
int d[100005]; //Distance from the root in DSU
vector<int> b[100005]; //Linear basises for connected components
void 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;
}
}

}```