Yet Another Rick and Morty Adventure

All submissions for this problem are available.
Rick Sanchez of earth dimension C137 has found out an anomaly created by the TransDimensional Council of Ricks which is consistent with all the dimensions in all timelines. They have started created links between different universes so that they could unify all the earths and take over the universe as OmniRick. Rick C137 clearly knows that if this happens, he will lose his own mind and become one with the OmniRick. Therefore, he sets on an adventure to stop this madness with Morty. The only way this linking is going to stop is that Rick C137 has to find something he calls the *MaXOR key*. This key will change every time any two universes are merged. Morty tells Rick that there are $N$ universes numbered from $1$ to $N$ and the Council has started created links between the universes. He gives him the details of the universes being merged. For e.g. if universe $1$ and $2$ are merged, they become part of one big universe with size 2. Consequently, if ($1$, $2$) and $3$ are merged, they would become an even bigger universe of size 3; Likewise, there are several links which are being processed. Morty tells him that there are $M$ different links which have been processed till now. The *MaXOR key* can be found by finding the maximum number which can be obtained by XORring the numbers of any nonempty subset of the set of sizes of linked universes. Obviously, Rick Sanchez can find out this key in a matter of seconds, but the problem is that he is too drunk to do it and therefore just wants the key without much effort. Can you calculate the key with the current information and give it to him? ###Input: The first line of the input contains 2 spaced integers $N$ and $M$. The next $M$ lines contains two spaced integers $U$_{i} and $V$_{i} which indicates the number of the two universes being merged. ###Output: Print a single integer, the MaXOR key which Rick requires to stop the formation of OmniRick ###Constraints  $2 \leq N \leq 10^5$  $1 \leq M < N$  $1 \leq U$_{i}, $V$_{i} $\leq N$ ###Subtasks  30 points : $1 \leq N \leq 100$ and $N  M \leq 5$  70 points : Original Constraints ###Sample Input: 5 3 5 1 2 3 5 4 ###Sample Output: 3 ###EXPLANATION: First we merge universes so we get: {5, 1, 4} and {2, 3} Now, we have 2 universes of size 2 and 3 respectively. Therefore the set of sizes is {2, 3} The XOR values for all nonempty subsets are: {2} = 2 {2, 3} = 1 {3} = 3 Thus, the MaXOR key is 3.Author:  enigma_abes 
Tags  enigma_abes 
Date Added:  27102018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions