题目描述

为了练习有向图的三种常见存储方式：邻接矩阵、邻接表、链式前向星，给定一个包含 $n$ 个顶点、$m$ 条有向边的图。

顶点编号为 $1,2,\ldots,n$。

接下来输入 $m$ 条有向边，每条边由两个整数 $u,v$ 表示：

u v

表示存在一条从顶点 $u$ 指向顶点 $v$ 的有向边 $u\rightarrow v$。

请依次输出每个顶点能够通过一条有向边直接到达的所有顶点。

本题中的“到达”只表示沿一条边直接到达，不要求计算经过多条边的传递可达关系。

为了让三种存图方式得到完全一致的结果，同一个顶点的所有邻接点必须按照顶点编号从小到大输出。

输入保证不存在重复的有向边，但允许出现自环，例如 3 3。

输入格式

第一行输入两个整数 $n,m$，分别表示顶点数和有向边数。

接下来 $m$ 行，每行两个整数 $u,v$，表示有向边 $u\rightarrow v$。

输出格式

输出 $n$ 行。

第 $i$ 行按从小到大的顺序输出顶点 $i$ 通过一条有向边能够直接到达的所有顶点编号，相邻两个编号之间用一个空格分隔。

如果顶点 $i$ 没有任何出边，则第 $i$ 行输出一个空行。

输入输出样例 #1

输入

5 6
1 2
1 4
2 3
4 2
4 5
5 5

输出

2 4
3

2 5
5

样例说明

• 顶点 1 可以直接到达 2、4；
• 顶点 2 可以直接到达 3；
• 顶点 3 没有出边，因此输出空行；
• 顶点 4 可以直接到达 2、5；
• 顶点 5 存在自环 5 -> 5。

数据范围

对于所有测试数据：

$1\le n\le 1000$

$0\le m\le \min(200000,n^2)$

$1\le u,v\le n$

输入保证不存在两条完全相同的有向边。

提示

邻接矩阵

可以使用：

bool graph[1005][1005];

若存在边 u -> v，则令 graph[u][v] = true。最后按 v=1..n 枚举即可自然得到升序输出。

邻接表

可以使用：

vector<vector<int>> graph(n + 1);

把每条边的终点加入 graph[u]。由于输入顺序不保证有序，输出前需要排序。

链式前向星

可以使用 head / to / next 数组记录边。链式前向星通常使用头插法，因此遍历顺序一般与输入顺序相反；本题可先收集某个顶点的所有邻接点，排序后再输出。