1430 - Sequence

Time Limit: 1s Memory Limit: 128MB

Submissions: 254 Solved: 162
Description

Given a sequence of N numbers, initially the numbers are 1, 2, 3…, N in order. And then there are M operations. Each operation belongs to one of two kinds below:

1 a b   swap the numbers in position a and position b.

2 a b   swap the numbers with value a and b.

You are to do these M operations in order, and then output the result sequence in a line.

Input

There are several test cases.

The first line an integer T indicating the number of test cases.

For each case, the first line is an integer N (2 <=N<=100) indicating the how many numbers there are in the sequence.

And then a line with an integer M indicating the number of operations. (1 <= M <= 100)

Then M lines following, each containing three numbers: either “1 a b” or “2 a b”, the meaning of which are as the description. (1 <= a, b <= N, a != b)

Output

For each case, output a single line in the following format:

Case #K: s[1], s[2], … s[N].

K is test case number start from 1, s[i] is the ith number in the result sequence.

Sample Input
2
4
3
1 1 3
2 1 4
1 2 3
2
2
1 1 2
1 1 2
Sample Output
Case #1: 3 4 2 1
Case #2: 1 2
Hint

For the first case:

Initially, the sequence is {1 2 3 4}

Operation 1, swap the numbers in position 1 and position 3: {3 2 1 4}

Operation 2, swap number 1 the number 4: {3 2 4 1}

Operation 3, swap the numbers in position 2 and position 3: {3 4 2 1}

So, the sesult sequence is {3 4 2 1}

Source