ÇïƮҶÁãµÄ²©¿Í

      ÌâÄ¿Á´½Ó£ºhttp://www.sicily.3322.org/sicily/show_problem.php?pid=1934

      ÕâÌ⿼²ìµÄÊÇÁ´±íµÄ»ù±¾²Ù×÷£¬¿¼Âǵ½Êý¾Ý¹æÄ£²»ÊÇÌ«´ó£¬ÓÃÊý×éʵÏÖºÃÁË£¬²»¹ýÕâÌâ Sicily µÄÊý¾ÝòËÆÓеãÎÊÌ⣬¼û´úÂëµÄ×¢ÊͲ¿·Ö£¬´úÂëÈçÏ£º


#include <iostream>
#include <cstdio>
using namespace std;

int prev[501000];
int next[501000];

int main()
{
    int t, n, m;
    int q, a, b;
    int counter, s;
   
    scanf("%d", &t);
   
    while (t --)
    {
         scanf("%d%d", &n, &m);
        
         for (int i = 1; i <= n + 1; i ++)
         {
              next[i - 1] = i;
              prev[i] = i - 1;
         }
        
         while (m --)
         {
              scanf("%d%d%d", &q, &a, &b);
             
              if (q == 1)
              {
                   next[prev[a]] = next[a];
                   prev[next[a]] = prev[a];
                  
                   next[prev[b]] = a;
                   prev[a] = prev[b];
                  
                   next[a] = b;
                   prev[b] = a;
              }
             
              else                           //ÕâÀï֮ǰÎÒдµÄÊÇ if (q == 2) ½á¹ûµÃµ½ÁË N ´Î WA£¬¸Ð¾õÊý¾ÝòËÆÓÐÎÊÌâ
              {
                   next[prev[a]] = next[a];
                   prev[next[a]] = prev[a];
                  
                   next[a] = next[b];
                   prev[next[b]] = a;
                  
                   next[b] = a;
                   prev[a] = b;
              }
         }
        
         counter = 1;
         s = next[0];
        
         while (counter <= n)
         {
              printf("%d ", s);
             
              s = next[s];
              counter ++;
         }
        
         printf("\n");
    }
   
    return 0;
}