Byteland is a tiny country, but has a big startup scene. Everyone starts their own one-person company in their garage and aims for success. But sometimes things do not work out so well, and the company is acquired by another, more successful business. Owners of two successful companies may also decide that they would be even more successful if they merged their businesses. In effect, the structure of corporations in Byteland is quite complex. When you meet two Byteland business people, it may not be obvious whether they are independent agents (strangers or competitors), or they are connected as members of the same large corporate group. To make things a bit more transparent, whenever there is a merger or acquisition involving two corporate groups, one representative from each company has to show up on the main square of Byteland, and the two shake hands, for everyone to witness the connection of the two hitherto separate corporate groups into one. Byteland laws prevent a single person from working for more than one company, so from the full public record of who shook hands with whom and when, you can figure out if two people at any point in time are from the same big corporate group, or not. Your task is to streamline this process, by designing an app to keep track of the mergers and acquisitions and to answer questions about who is connected to whom. Specifically, the application will load historical data on handshakes, and will be informed, in real time, of any new handshake between two people, and should be able to answer, in real time, if any two people represent the same corporate group, that is, can be linked by a chain of past handshakes.

As a working prototype to showcase the algorithm behind your app, write a Java program that takes the following input from System.in:

-First line of input is two numbers NM, separated by a space, where N the number of input lines to follow next, and M is total number of citizens of Byteland

-Each of the subsequent N lines will have three integers separated by space:

-0 A B, indicating that a person A just shook a hand with person B. This means that person A and everyone who is connected with person A is from now on connected to person B and to everyone who is connected with B.

-1 A B, indicating a query whether person A is connected with person B

For the input of type 0 A B there should be no outputjust internal update of the data structures.

For the input of type 1 A B, there should be one line of output to System. out, with 0 if A and B are not connected, and 1 if they are.

Hint: Use the Disjoined Sets data structure.

Constraints:

-1<= N <= 1000

-2 <= M <=1000

-0 <= A, B <= M-1 (Byteland citizens have unique IDs, integers 0 to M-1)

-Use of any libraries/packages for tree-/list-/graph-like data structures, or of any tree/list/graph algorithms, is not allowed.