An undirected graph has n vertices, numbered 0 to n - 1, and m edges. Print the degree of every vertex: the number of edges that touch it. No edge is repeated, and no edge joins a vertex to itself.
What to build
The degree of each vertex, counted while the edges are read.
Requirements
- Add one to both ends of every edge.
- Print the degrees in vertex order.
Input
The first line has n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Each of the next m lines has an edge u v.
Output
The n degrees, in vertex order, separated by spaces.
Constraints
1 ≤ n ≤ 100 and 0 ≤ m ≤ 1000.
Example
Input:
4 4
0 1
0 2
1 2
2 3
Output:
2 2 3 1
Why it works
Each edge touches exactly two vertices, so it adds one to each of their degrees. The graph itself never needs to be stored.
Examples
Example 1 · Input
4 4 0 1 0 2 1 2 2 3
Expected output
2 2 3 1
Example 2 · Input
3 0
Expected output
0 0 0
Hints
Hint 1
You do not need to store the graph: each edge u v adds 1 to the degree of u and 1 to the degree of v.
Hint 2
Start the degree array at zero: int degree[100] = {0};
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
int degree[100] = {0};
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
degree[u]++;
degree[v]++;
}
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", degree[i]);
}
printf("\n");
return 0;
}