DMOPC '23 Contest 1 P6 - Sky Clearing Up

View as PDF

Submit solution

Points: 35 (partial)
Time limit: 10.0s
Memory limit: 1G

Problem type

The city of Lletya is known for its violent and unpredictable weather. As a result, residents cannot go outside to meet one another in-person, and are forced to communicate with telephones. To ease communications, the government of Lletya built a network of N phone switch stations, which calls are forwarded through. As lightning can interfere with wireless signals, switch stations are physically connected with telephone wires. As maintenance is expensive, switch stations are connected with as little wire as possible, so there is exactly one way to forward a call between any two switch stations.

Lletya outsources its switch stations to M phone companies. The i-th phone company owns B_i of the N switch stations, though multiple companies can own the same station. A call between residents subscribed to the i-th phone company must enter and leave through a pair of switch stations company i owns. Of course, the call can be transmitted through switch stations not owned by company i, as long as company i owns the starting and ending stations. A call can enter and leave the same switch station.

A switch station can only process one call at a time: whether it be sending, receiving, or transmitting the call: calls conflict if they need to use the same switch station. We say that company i interferes with company j if a call under company i can conflict with a call under company j, or vice versa. Consider the set of 9 switch stations wired in the diagrams below, and suppose that company 1 owns stations \{1,6\}, company 2 owns stations \{4,8\} and company 3 owns stations \{5,8,9\}. Then company 1 interferes with company 2, since a call between stations 1 and 6 under company 1 conflicts with a call between stations 4 and 8 at station 3 (see left diagram). Company 2 interferes with company 3 since a call between stations 4 and 8 under company 2 conflicts with a call between stations 5 and 9 under company 3 at station 5 (see right diagram). However, no call under company 1 can conflict with a call under company 3, so companies 1 and 3 do not interfere.

While residents heavily dislike interferences, they are forced to tolerate them. However, one rainy morning, the dark clouds above Lletya began to part. As the sky cleared and violent storms ceased, residents left their homes to meet in-person instead of over the phone. As a result, the government plans to shut down some phone companies to cut costs.

Companies are not happy with this, so the government must provide a good reason for each shutdown. Namely, if companies i and j are both shut down, then they must interfere with one another (the government can use delays from interference as an excuse). Moreover, the government also wants to prevent one of the remaining phone companies from becoming too profitable: thus, for any triplet of companies i,j,k remaining after the shutdown, if company i interferes with company j, and company j interferes with company k, then company i must interfere with company k.

Is there a non-empty set of companies the government can shut down?


1 \le T \le 10^5

1 \le N,M \le 120\ 000

1 \le B_i \le N

\sum_{i=1}^{M} B_i \le 250\ 000

It is guaranteed that the sum of N over all test cases will not exceed 500\ 000.

It is guaranteed that the sum of M over all test cases will not exceed 500\ 000.

It is guaranteed that the sum of \sum_{i=1}^{M} B_i over all test cases will not exceed 10^6.

Subtask 1 [10%]

The switch stations are wired in a line (more precisely, stations i and i+1 are connected for all 1 \le i \le N-1).

Subtask 2 [15%]

There is at most one switch station of degree >2.

Subtask 3 [75%]

No additional constraints.

Input Specification

On the first line, an integer T, the number of test cases.

The first line of each test case contains two space-separated integers N and M, the number of switch stations and phone companies in Lletya.

The next N-1 lines each contain two space-separated integers, x and y (1 \le x,y \le N,\, x \neq y), indicating that stations x and y are connected with wires.

The next M lines each contain an integer B_i, the number of stations company i owns, followed by B_i unique space-separated integers t_1,\ldots,t_{B_i} (1 \le t_j \le N), the stations company i owns.

Output Specification

For each test case, output one line, consisting of an integer k (1 \le k \le M), followed by k unique space-separated integers s_1,\ldots,s_k (1 \le s_i \le M), indicating a possible non-empty set of companies the government can shut down. If there are multiple answers, output any of them. If there is no non-empty set of companies the government can shut down to meet its requirements, output -1.


If your program outputs -1 for impossible cases, but an incorrect set of companies otherwise, the grader will award 75\% of the points for the test case.

If your program outputs a malformatted set of companies (for example, if k \le 0, or \{s_1,\ldots,s_k\} contains repetitions), the grader will throw a Presentation Error.

Sample Input

5 5
1 2
2 3
3 4
4 5
2 1 2
1 2
2 2 3
3 2 3 4
2 3 5
9 3
1 2
2 3
3 4
3 5
3 6
6 7
5 8
5 9
2 1 6
2 4 8
3 5 8 9
13 8
1 2
2 3
2 4
4 5
5 6
6 7
7 8
8 9
7 10
10 11
10 12
10 13
3 2 5 6
4 2 4 5 6
2 1 7
5 4 6 7 10 13
3 7 8 9
2 11 12
3 10 11 12
2 2 3

Sample Output

2 3 4
1 2
2 3 4

Explanation for Sample

For test case 1, a call from station 2 to 3 under company 3 and a call from station 3 to 4 under company 4 both need to use station 3. Thus, companies 3 and 4 can both be shut down.

Test case 2 is described in the problem statement.

Test case 1 satisfies the constraints of all 3 subtasks.

Test cases 2 and 3 satisfy the constraints of subtask 3.


There are no comments at the moment.