DMOPC '15 Contest 6 P6 - Graf Zeppelin

View as PDF

Submit solution


Points:15 (partial)
Time limit:3.0s
Memory limit:256M
Author:

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


  • 0
    Cueball1234
     commented on Sept. 12, 2017 edited

    QU

    For the moment, I am QUing, preventing me from making any new submissions. Is there a reason for this? Thank you!

    Edit: It is all good now.


  • 0
    Cueball1234
     commented on Sept. 3, 2017 edited

    Internal Error?

    Edit: nvm, it works now


  • 1
    minecraftyugi
     commented on March 7, 2016
    Time Limits

    Is this question solvable in python?


  • 0
    FatalEagle
     commented on March 1, 2016 edit 4
    Data is fixed

    Test data is fixed. If you were affected by this issue, you should email the admin on finding a resolution.


    • 1
      arock
       commented on March 1, 2016 edited

      In test case 2 I believe K = 0, contrary to the problem statement.


      • 1
        FatalEagle
         commented on March 1, 2016

        You're right. I overlooked that, sorry. It will be fixed in the final tests.