题目描述

给定一张由 $n$ 个点和 $m$ 条有向边组成的图，每条边长度均为 $1$。

指定点 $x$ 为起点，求它到其他所有点的最短距离，并按距离给所有点分级：距离相同的点属于同一级。点 $x$ 自成距离为 $0$ 的一级；从 $x$ 无法到达的点距离视为无穷大，统一放在最后一级。

每一级中的结点按编号从小到大输出。

输入格式

第一行输入三个正整数 $n,m,x$。接下来 $m$ 行，每行输入两个正整数 $s,t$，表示一条从 $s$ 到 $t$ 的有向边。

输出格式

输出若干行，每行输出同一级的所有结点编号，编号之间用一个空格分隔。按距离从小到大输出各级，不可达结点所在级最后输出；空级不输出。

输入输出样例 #1

输入 #1

67 261 38
1 12
2 28
2 30
3 34
3 41
4 15
5 28
5 46
5 47
5 63
6 7
6 18
7 22
8 7
8 33
8 37
8 47
8 48
9 26
9 33
9 35
9 52
9 65
10 4
10 22
10 58
11 10
11 44
12 1
12 19
12 20
12 53
13 26
13 27
13 30
13 34
14 2
14 6
14 11
14 27
14 43
14 54
14 60
14 63
15 5
15 8
15 18
15 26
15 34
15 50
16 21
16 30
16 39
16 47
16 61
16 66
17 6
17 31
17 63
18 35
19 27
20 1
20 5
20 18
20 24
20 31
20 32
21 11
21 27
21 44
21 65
22 14
22 20
22 26
22 28
22 58
23 8
23 12
23 38
23 46
23 47
23 49
23 62
23 67
24 3
24 59
24 60
25 23
26 4
26 28
26 36
26 46
26 53
27 13
27 18
27 29
27 39
27 41
27 52
27 57
27 63
28 8
28 15
28 16
28 57
29 19
29 55
30 10
30 12
30 28
30 61
30 63
31 52
31 53
32 28
32 45
33 26
33 36
33 48
34 4
34 8
34 15
34 16
34 26
34 42
34 60
34 65
35 12
35 58
36 24
36 28
36 58
36 60
37 22
37 41
37 64
37 67
38 45
38 54
38 55
38 59
39 3
39 16
39 17
39 39
39 46
39 64
40 24
40 27
40 36
40 38
40 66
41 3
41 6
41 44
41 52
42 11
42 38
43 2
43 48
43 55
43 65
43 66
45 14
45 27
46 7
46 25
46 35
46 36
46 46
46 63
46 66
47 14
47 20
47 30
47 57
48 13
48 62
48 63
49 3
49 32
49 39
49 47
50 45
50 54
50 64
50 65
51 24
51 40
51 48
53 10
53 41
53 63
54 25
54 45
54 46
54 62
54 67
55 10
55 18
55 21
55 66
56 13
56 16
56 25
56 39
56 45
57 23
57 25
57 37
58 38
58 52
58 57
58 61
59 9
59 25
59 46
59 49
59 65
60 20
60 57
60 66
61 14
61 24
61 26
61 60
62 22
62 29
62 30
62 35
62 41
62 46
62 50
62 58
62 62
63 11
63 21
63 23
63 36
63 42
63 44
63 53
64 6
64 21
64 23
64 43
64 49
65 6
65 18
65 52
65 67
66 8
66 15
66 21
66 34
66 55
66 61
67 42
67 48
67 58
67 59

输出 #1

38
45 54 55 59
9 10 14 18 21 25 27 46 49 62 65 66 67
2 3 4 6 7 8 11 13 15 22 23 26 29 30 32 33 34 35 36 39 41 42 43 44 47 48 50 52 57 58 60 61 63
5 12 16 17 19 20 24 28 37 53 64
1 31
40 51 56

输入输出样例 #2

输入 #2

6 2 1
5 1
5 2

输出 #2

1
2 3 4 5 6

输入输出样例 #3

输入 #3

71 81 1
2 16
2 64
4 14
4 39
5 1
5 66
6 17
6 43
8 38
10 50
10 62
11 13
11 22
11 24
11 60
12 44
13 44
14 14
14 28
15 67
16 9
16 27
17 28
17 64
17 68
19 20
19 28
20 57
21 29
22 19
22 62
23 19
23 37
24 65
25 15
25 38
25 61
25 70
26 30
26 63
26 71
29 46
29 63
31 28
32 17
33 5
33 40
37 22
38 30
39 1
40 9
41 5
44 22
47 67
50 35
52 28
52 56
54 29
54 60
55 17
55 22
56 14
56 65
57 3
57 40
58 24
59 20
59 70
60 43
61 13
62 34
63 5
63 31
63 62
64 56
65 42
67 4
69 38
69 56
70 53
71 1

输出 #3

1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

数据范围与约定

$1\le n\le10^5$，$1\le m\le10^6$。