题目描述

一个稀疏有向图中有n个点（编号为1~n），m条边，请读入m条边，按照结点编号从小到大的顺序，输出每个点的出度和入度。

输入格式

第1行有2个整数，n和m，代表有n个点，m条边；（n≤1,000,000，m≤10,000）； 接下来 m 行，每行有2个整数x,y，代表x到y之间存在一有向条边（x,y≤n） 本题测试数据确保任意两点之间最多只有1条边、且数据合法，不存在x点到x点有边的情况。

输出格式

按照结点编号从小到大的顺序，输出每个点的编号，再输出这个点的出度和入度（如果该点没有出边和入边，则该点不输出） 。输出格式请参考本题的样例。

样例

输入样例 1

50 6
3 1
1 2
2 4
3 4
4 5
20 9

输出样例 1

1 1 1
2 1 1
3 2 0
4 1 2
5 0 1
9 0 1
20 1 0

输入样例 2

5 8
1 2
2 3
2 4
1 3
1 4
4 3
3 5
4 5

输出样例 2

1 3 0
2 2 1
3 1 3
4 2 2
5 0 2

输入样例 3

50 8
1 2
2 3
2 4
1 3
11 4
4 31
3 5
4 50

输出样例 3

1 2 0
2 2 1
3 1 2
4 2 2
5 0 1
11 1 0
31 0 1
50 0 1