DMOPC '15 Contest 6 P6 - Graf Zeppelin

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.4s
Memory limit: 256M
Author:
FatalEagle
Problem type

Graf has a graph, a graph with N vertices and M bidirectional edges. In this graph, Graf wonders: for each vertex how many vertices are within distance K of it?

Input Specification

The first line will have space-separated N (1 \le N \le 1\,500), M (1 \le M \le \frac{N \times (N-1)}{2}), and K (1 \le K \le 5).
The next M lines will describe the edges: there is an edge between every pair of integers on the next M lines. Edges will not be repeated in the input.
10\% of the test data will additionally have N \le 200.

Output Specification

Output N lines, the answer for vertex number i on line i.

Sample Input 1

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

Sample Output 1

3
5
3
4
2
3

Sample Input 2

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

Sample Output 2

4
4
4
4

Comments


  • 1
    minecraftyugi  commented on March 7, 2016, 2:20 p.m.

    Is this question solvable in python?