Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

你有一些小球，从左到右依次编号为1,2,3,...,n. 你可以执行两种指令（1或者2）。其中， 1 X Y表示把小球X移动到小球Y的左边， 2 X Y表示把小球X移动到小球Y右边。 指令保证合法，即X不等于Y。 例如，初始状态1,2,3,4,5,6的小球执行1 1 4后，小球1被移动到小球4的左边，即2,3,1,4,5,6。如果再执行2 3 5，结点3将会移到5的右边，即2,1,4,5,3,6。 

Input

第一行为一个整数t（0<t<10），表示测试用例个数。每个测试用例的第一行为两个整数n（1<n<=500000）和m（0<m<100000），n表示小球的个数，m为指令条数，以下m行每行为一条指令。 

Output

为每个测试用例单独输出一行，从左到右输出最后序列，每个数字后面跟一个空格。 

Sample Input

2 
6 2 
1 1 4 
2 3 5 
5 1 
2 1 5 

Sample Output

2 1 4 5 3 6  
2 3 4 5 1  

0.26s：

#include <stdio.h>

int l[500005], r[500005];

void do_order(int order_num) {
    int kind, x, y;
    while (order_num--) {
        scanf("%d%d%d", &kind, &x, &y);
        
        r[l[x]] = r[x];//首先x球的位置两边要处理
        l[r[x]] = l[x];
        
        if (kind & 1) {
            r[l[y]] = x;//然后新插入位置的两个球以及它自身要处理
            l[x] = l[y];
            l[y] = x;
            r[x] = y;
        } else {
            l[r[y]] = x;//同上
            r[x] = r[y];
            r[y] = x;
            l[x] = y;
        }
    }
}



void print(int n) {
    
    int temp = 0;
    while (n--) {
        
        temp = r[temp];//每次输出球的右边的球就是最后的顺序
        printf("%d ", temp);
        
    }
    printf("\n");
}

int main() {
    int case_num, n, order_num;
    scanf("%d", &case_num);
    while (case_num--) {
        scanf("%d%d", &n, &order_num);
        r[0] = 1;
        for (int i = 1; i <= n; i++) {
            l[i] = i - 1;
            r[i] = i + 1;
        }
        do_order(order_num);
        print(n);
    }
    return 0;
}