Description

关系R具有对称性和传递性。数对p q表示pRq,p和q是0或自然数,p不等于q。 要求写一个程序将数对序列进行过滤，如果一个数对可以通过前面数对的传递性得到，则将其滤去。例如： 输入    输出 	  连通性 3 4      3 4    4 9      4 9 8 0      8 0 2 3      2 3 5 6      5 6 2 9                     2-3-4-9 5 9      5 9 7 3      7 3 4 8      4 8 5 6                     5-6 0 2                     0-8-4-3-2 6 1      6 1

 其中数对2 9和0 2可由之前数对的连通关系得到，故不做输出。

Input

输入共有m行(0<=m<=1000000),每行一个数对，数对的数字之间以1个空格分隔；数对的数字为0或n=100000以内的自然数。

 

Output

输出包含过滤之后的数对序列。每行输出一个数对，数对的数字之间以1个空格分隔。

 

Sample Input

 Copy sample input to clipboard

3 44 98 02 35 62 95 97 34 85 60 26 1

Sample Output

3 44 98 02 35 65 97 34 86 1

//在本题中要删去所有具有连通性的结点，而具有连通性的结点的性质是//在图中具有相同的祖先，则我们只要通过判断两个结点是否存在相同的祖先//即可判断是否需要删去，最直接的做法是每插入一对结点，DFS或BFS，判断是否搜索到相同的点//但这样做法时间复杂度太大，在一开始时就让每个结点指向自己的祖先结点#include
      
       using namespace std;const int MAX = 1000005;int father[MAX];int find(int num) {return ( num==father[num] ? num : (father[num]=find(father[num])) );}int main(){    int m;    for(int i=0;i
       
        >point1>>point2)    {        if(find(point1)!=find(point2))        {            cout<
        
         <<" "<
         
          <