a. You have 5 problems in this assignment.

b. G++ compiler will be used to compile your source codes.

c. Your program will be tested on Ubuntu 16.04. d. You are not allowed to use global variables in your implementation. e. Your program will get two arguments, input and output file names, from the command line: >> Your_Executable INPUT_FILE_NAME OUTPUT_FILE_NAME

1.

Given a number , we initially have +1 different sets which are {0}, {1}, {2}, ... , {}.

Your program should support two operations on those sets: 1) union two sets, and 2) check whether two elements are contained by the same set. Input: In the first line, two integers (1

The following lines specify the operations.

A line having a format of 0 indicates a union operation of set and set containing elements and , respectively ( , ).

Similarly, a line beginning with 1 ask you to check whether and are in the same set. Output: For each checking operation, you are required to answer Y if two elements are in the same set. Otherwise, print N.

Sample input 6 5 1 0 3 0 1 2 0 3 4 0 1 4 1 2 3

Sample Output N Y

2.

Given a weighted undirected graph, provide the cost of a minimum spanning tree. Input: In the first line, two integers (1

The following lines describes edges in a format of indicating that the graph has an edge between vertices and with cost of .

Note that the vertex index begins with 1 and the cost can be negative but ||

Sample input 3 3 1 2 1 1 3 2 2 3 3

Sample Output 3

3.

Given a weighted undirected graph, provide the cost of the second minimum spanning tree.

The second minimum spanning tree has the minimum cost except MSTs.

In the figure, the left and right subfigures show the MST and the second MST, respectively.

Input: In the first line, two integers (1

The following lines describes edges in a format of indicating that the graph has an edge between vertices and with cost of .

Note that the vertex index begins with 1 and edge weights are positive.

Output: You are required to output the cost of the second minimum spanning tree. You can output "-1 if such tree does not exist.

Sample Input

7 12 1 2 8 1 3 5 2 3 10 44 2 4 2 2 5 18 3 4 3 3 6 16 4 5 12 4 6 30 4 7 14 5 7 4 6 7 26

Sample Output

44

4.

We have a network which is defined by the dependency and data transfer time among computers.

For instance, if a computer depends on a computer with the transfer time , then any data can be transferred from to in seconds.

Unfortunately, a computer in our network is infected with a virus. The virus will be propagated to the other computers which depend on the infected computers. When a computer is just infected, the computer will be infected after seconds, if depends on with time .

We want to determine the number of computers that will be infected and the last time of infection from the first infection.

Input: In the first line, three integers (1

The following lines describe dependencies in a format of indicating that the computer depends on with transfer time of , where " and 0

Note that the vertex index begins with 1 and you can assume that the dependency is unique.

Output: You are required to output the number of infected computers and time of the last infection from the first infection

Sample input 3 3 1 2 1 2 3 1 8 3 2 4

Sample Output

3 6

5.

We would like to cross over a river by stepstones. The position of a stepstone is represented by (, ). You can jump to another stepstone, however, you have certain constraint due to your physical ability. When you are at (, ), you are only allowed to jump to stones at (, ) where | - |

For instance, you can jump from (0,0) to (2,2) or (2,1) , but you cannot move to (3,0).

The goal is reaching a line which is parallel to -axis. You are required to find a shortest path from (0,0) to the goal line in terms of the sum of distances.

The distance between two stones at (, ) and (, ) is the Euclidean distance

Input: In the first line, two integers (1

The following lines describe the position of stepstones in a format of where and are integers. Note that 0

Output: Provide the distance of shortest path by rounding off to the nearest integer. (The exact distance in the following sample is 8.47 . You need to answer 8 by rounding off the exact distance.)

Sample input 5 3 1 2 6 3 4 1 3 2 0 2

Sample Output

8