問題文

頂点数 N、辺数 M のグラフが与えられます。頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 A_i と B_i を双方向に結んでいます。 それぞれの k について、「頂点 k と隣接している頂点の番号」をすべて出力するプログラムを作成してください。

制約

• 2 \leq N \leq 100000
• 1 \leq M \leq 100000
• 1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
• i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
• 入力は全て整数

入力例 1

5 4
1 2
2 3
3 4
3 5

出力例 1

1: {2}
2: {1, 3}
3: {2, 4, 5}
4: {3}
5: {3}

与えられたグラフは次のようになります。

たとえば 2 行目については、2: {1, 3} ではなく 2: {3, 1} と出力しても正解となります。

入力例 2

15 30
6 9
9 10
2 9
9 12
2 14
1 4
4 6
1 3
4 14
1 6
9 11
2 6
3 9
5 9
4 9
11 15
1 13
4 13
8 9
9 13
5 15
3 5
8 10
2 4
9 14
1 9
2 8
6 13
7 9
9 15

出力例 2

1: {3, 4, 6, 9, 13}
2: {4, 6, 8, 9, 14}
3: {1, 5, 9}
4: {1, 2, 6, 9, 13, 14}
5: {3, 9, 15}
6: {1, 2, 4, 9, 13}
7: {9}
8: {2, 9, 10}
9: {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15}
10: {8, 9}
11: {9, 15}
12: {9}
13: {1, 4, 6, 9}
14: {2, 4, 9}
15: {5, 9, 11}