Sequence

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.