DMOPC '21 Contest 4 P5 - Graph Generator

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Allen, Nella's older brother, has a better way of building graphs; he plugs them into his graph generator! The generator takes 3 items as input:

  1. An initial graph G consisting of N nodes labeled from 1 to N connected by M distinct undirected edges of length 1.
  2. An array P of length N, where P_i = 1 if nodes labeled i are producers and P_i = 0 otherwise.
  3. A positive integer K, the number of generation phases.

The generator then begins building the graph, happening in K generation phases. In the first phase, the graph G is constructed. Then, for every phase after the first, the generator does the following:

For every node u that is a producer constructed in the previous phase, construct a copy of G and connect node 1 of the copy to u with an undirected edge of length 1.

To estimate the size of the graph constructed after the K-th generation phase is over, compute the sum of the lengths of the shortest paths between every pair of nodes.


1 \le N \le 3 \times 10^3

0 \le M \le 3 \times 10^3

1 \le K \le 10^6

P_i \in \{0, 1\}

1 \le u_j, v_j \le N

G is connected.

\sum_{i = 1}^N P_i \ge 1

Subtask 1 [20%]

\sum_{i = 1}^N P_i = 1

Subtask 2 [30%]

M = \frac{N(N - 1)}{2}

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains 3 integers N, M, and K.

The second line contains N integers P_1, P_2, \dots, P_N.

The next M lines each contain 2 integers u_j and v_j, the labels of the endpoints of the j-th edge in G. All edges are distinct, and there are no self-loops.

Output Specification

Output the sum of the lengths of the shortest paths between every pair of nodes. Since this value may be large, output it modulo 10^9 + 7.

Sample Input

2 1 2
1 1
1 2

Sample Output



There are no comments at the moment.