Description

Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order. Each node has unique integer identification (ID), but all IDs may not be consecutive.

Input

There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000), denoting the number of relations in the tree. In the following N lines, each line contains two integers a and b (1 <= a,b <= 1000), which means node a is node b’s parent. After that, the next line contains an integer R, which represents the root of the tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.

Output

For each test case, print the pre-order of the tree. In each level, traverse the node with smaller ID first.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a decimal integer n and a base k, translate n to the corresponding k-based number.

Input

 The first line contains an integer t (1 <= t <= 100), which indicates the number of test cases in the input. Each test case is given in a line, containing two integers n and k (n <= 10000000, k<=9).

case1: n<=100
case2: n<=10000
case3: n<=100000
case4: n<=10000000

Output

 Output the number in base k.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You will be given an IC design graph with several connected chips components. In order to improve the design, your job is to find out the component with the largest number of chips. A connected chips component is a subset of chips in which any two chips are connected to each other by paths, and which is connected to no additional chips.

Input

There will be several test cases. In each test case, the first line will be an integer N representing the number of chips. The second line contains an integer K which is the number of wires. In the next K lines, each line contains two integers, A and B (0 <= A, B < N), which denotes that there is a wire between chip #A and chip #B. If N = 0, the input ends. Chips are numbered from 0~N-1.
Case 1: 1<=N<=10, 1<=K<=N^2
Case 2: 1<=N<=100, 1<=K<=N^2
Case 3: 1<=N<=1000, 1<=K<=min {N^2, 100000}
Case 4: 1<=N<=200000, 1<=K<=min {N^2, 200000}

Output

For each design graph, print the number of chips for the largest connected chips component.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Compute C=AB, where A is a matrix of size m×n, B is a matrix of size n×p, and C is a matrix of size m×p.

Input

First line contains a positive integer t (t <= 50), which indicates the numbers of test cases in the input. The first line of each test case contains three positive integers m, n, p (m, n, p <= 100) for the dimension of matrices. In the next m lines, each line contains n integers, representing the elements of matrix A. Followed by n lines, each line containing p integers, represent the elements of matrix B. All elements of A and B are integers in the range [-2²⁰, 2²⁰].


Case 1: m, n, p <=50, All elements of A and B are integers in the range [-2¹⁰, 2¹⁰].
Case 2: m, n, p <=100, All elements of A and B are integers in the range [-2¹⁰, 2¹⁰].
Case 3: m, n, p <=50, All elements of A and B are integers in the range [-2²⁰, 2²⁰].
Case 4: m, n, p <=100, All elements of A and B are integers in the range [-2²⁰, 2²⁰].

Output

For each case, output an m*p matrix in m lines and each line contains p integers.
Use one space between two consecutive integers. Output a blank line after each case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input will give you a lot of “multi dimension” points, and your mission is to find the minimum distance of all the possible pairs.
The point will give you as follows:
If a 5-dimension point like (1,0,0,3,2), I will give the (index,value) pair in a single line such as (1,1);(4,3);(5,2)

And you can assume that the dimension of each test case is same, because you can fill zero as you want. This means that (1,0,0,3,2) may become 7-dimension such as (1,0,0,3,2,0,0)

And the distance means the Manhattan distance.
P1(p11,p12,p13,p14)
P2(p21,p22,p23,p24)
The distance of P1 and P2 is abs(p11-p21)+abs(p12-p22)+abs(p13-p23)+abs(p14-p24)

abs means the absolute value.

Input

The input includes multiple test cases. In each test case, there are many lines, each line represent a point in the format: (index1,value1);(index2,value2);…(indexM,valueM)
After all the points, ther is a single line “END” represent the ending of this test case.
See the sample input clearly.

The number of points : N
The range of index : idx
The number of pair in a single line I will give you : D
The value of the point : val

case 1: 2<=N<=10, 1<= idx <=5, 1<=D<=5, 0<=val<=100
case 2: 2<=N<=50, 1<= idx <=50, 1<=D<=50, 0<=val<=10^4
case 3: 2<=N<=50, 1<= idx <=10^4, 1<=D<=300, 0<=val<=10^6
case 4: 2<=N<=100, 1<= idx <=10^6, 1<=D<=10^3, 0<=val<=10^8

For example, in case 3, there may be a test case that has 50 points, and each point in the format:
(index1,value1);(index2,value2);…(indexM,valueM)
Then 1<=index1,index2,…indexM<=10^4,
And 0<=value1,value2,…valueM<=10^6
And D = 300 means each point I will give you at most 300 pairs, that is 1<=M<=300.

Output

For each test case, output the minimum distance of all the possible pairs.

Sample Input  Download

Sample Output  Download

Tags

Discuss