1539 : 牛牛的猜球游戏

牛牛和牛妹在玩猜球游戏,牛牛首先准备了10个小球，小球的编号从0~9。首先牛牛把这10个球按照从左到右编号为0,1,2,3...9的顺序摆在了桌子上，接下来牛牛把这10个球用10个不透明的杯子倒扣住。
 牛牛接下来会按照一定的操作顺序以极快的速度交换这些杯子。
 换完以后他问牛妹你看清楚从左到右的杯子中小球的编号了么？
 
  由于牛妹的动态视力不是很好，所以她跑来向你求助。你在调查后发现牛牛置换杯子其实是有一定原则的。 
  
 
  具体来讲，牛牛有一个长度大小为n的操作序列。
 
  
 
  操作序列的每一行表示一次操作都有两个非负整数a,b，表示本次操作将会交换从左往右数第a个杯子和从左往右数第b个杯子（a和b均从0开始数）。请注意是换杯子，而不是直接交换a号球和b号球 
  
 
   牛牛和牛妹一共玩了m次猜球游戏，在每一轮游戏开始时，他都将杯子中的小球重置到从左往右依次为0,1,2,3...9的状态。
 然后在第i轮游戏中牛牛会按照操作序列中的第$l_i$个操作开始做，一直做到第$r_i$个操作结束（l和r的编号从1开始计算）。
 由于你提前搞到了牛牛的操作序列以及每一次游戏的l,r。请你帮助牛妹回答出牛牛每一轮游戏结束时，从左至右的杯子中小球的编号各是多少。

首先输入一行两个正整数n,m，表示操作序列的长度以及进行游戏的次数。
接下来n行每行两个非负整数a,b，表示交换左数第a个杯子和左数第b个杯子。(a,b均从0开始数起)
接下来m行每行两个正整数l,r表示该轮游戏中牛牛从第l个操作开始做，一直做到第r个操作结束。（l和r的编号从1开始计算）

对于每一轮游戏，输出一行10个非负整数，表示从左至右每一个杯子中小球，输出的整数之间用空格隔开，行末不允许有多余空格。

5 3
0 1
1 2
2 3
0 1
9 0
1 5
5 5
3 5

9 1 3 0 4 5 6 7 8 2
9 1 2 3 4 5 6 7 8 0
9 0 3 2 4 5 6 7 8 1

对于100%的测试数据，保证$1 \leq n,m \leq 10^5,0 \leq a,b \leq 9 ,1 \leq l\leq r \leq n, 1≤n,m≤10^5 ,0≤a,b≤9,1≤l≤r≤n$

day4