离散题目18

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给出一个集合A和A上的关系R,求关系R的传递闭包。

例如:

A={0,1,2} , R={<0,0>,<1,0>,<2,2>,<1,2>,<2,1>}   

t(R) = {<0,0>,<1,0>,<2,2>,<2,1>,<1,2>,<1,1>,<2,0>};

Input

多组输入,输入n、m,集合A={0, 1, …, n-1 };m代表关系的数量,n、m不超过20.

Output

每组输入输出t(R),根据t(R)中序偶的第一个数字升序排序,如果第一个数字相同,根据第二个升序排序。

Sample Input

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

Sample Output

0 0
1 0
1 1
1 2
2 0
2 1
2 2

Hint

Source