题目描述

给出一个有向图 $G$（无重边/自环），请你构造这个图 $G^2$。

• 如果在原图 $G$ 中存在的 $2$ 条有向边<u,v>和<v,w>, 则 $G^2$ 中存在有向边<u,w>，即 $G^2$ 中的边对应于 $G$ 中恰走两步可以到达的点对。

输入格式

第一行包含2个整数N、M，表示该图共有N个结点和M条有向边。（N <= 500，M <= 100000）

接下来M行，每行包含3个整数{u,v,w}，表示有一条长度为w的有向边<u,v>，u指向v。

输出格式

N行，顶点按照1~n编号从小到大输出每个点的邻接点构成的边。如果对于某个顶点i，没有出边，输出空行。注意，对于从u出发的所有边<u,v>，输出的时候，要按照v从小到大排序。

4 4
1 2 2
1 4 1
2 3 4
3 1 3

<1,3>
<2,1>
<3,2> <3,4>

数据规模与约定

• 输出需要保证平方图中没有重边
• 样例1：注意输出有4行，第四行是空行
• 样例2：注意输出有4行
• $G^2$ 中可能有自环， 也需要输出