传递闭包（2022秋）

题目描述

经常有同学能认出花叶小姐姐，但是花叶小姐姐并不能认出对方，为此花叶小姐姐很苦恼。

所以花叶小姐姐决定狠狠的单向开盒。

假设花叶小姐姐单向开盒了$A$，$A$单向开盒了$B$，那么我们认为花叶小姐姐也单向开盒了$B$。

自己不一定单向开盒自己

花叶小姐姐将你软所有同学都排了一个序号，序号为$1$到$n$。

下面给出花叶小姐姐知道的你软这$n$个人的部分单向开盒状态，

希望你帮助花叶小姐姐确定你软这$n$个人实际所有的单向开盒状态。

说白了就是给出关系$R$，希望你求出其传递闭包。

要求使用Python编写程序

输入

第一行两个整数，第一个数是你软所有同学的数量$n$，第二个数是花叶小姐姐目前了解到的单向开盒的情况数量$m$

接下来$m$行，每行$2$个整数$u\ v$，表示你软编号为$u$的同学单向开盒了编号为$v$的同学

输出

按照编号从小到大的顺序输出所有的单向开盒情况。

输入样例1

3 3
1 2
2 3
3 1

输出样例1

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

输入样例2

4 3
1 3
2 4
3 4

输出样例2

1 3
1 4
2 4
3 4

数据范围

$3\leq n \leq 100$

$1\leq m \leq 1000$

Hint

1. 可以参考《算法导论》第405页 图算法 25.2节 Floyd-Warshall算法改改试试。

2. 要求使用Python编写程序，不需要使用import

3. 提交的时候，你的Python版本是多少，在语言选择处就选择多少。

   比如你的Python版本是3.9，那么选择语言就选择Python3。