This page is still under construction.

Parts of this page are still being built. What you see may change.

Cookie Run: Kingdom

Time limit1sMemory limit512 MB

Summary
Given which resource types each building produces and which resources each unbuilt building needs, count the buildings constructible within T seconds starting from the M already-built ones.
Level

Medium6 of 10

Topics
Graph, BFS, Hash map, Simulation
Solved
No attempts yet

Problem

My friend Brave Cookie is troubled. These days Brave Cookie plays a game called Cookie Run: Kingdom, where buildings are constructed using some of the NN kinds of resources numbered 1,2,⋯ ,N1, 2, \cdots, N. A resource can be produced without cost and without limit through buildings that are already built, and the building that can produce each resource is fixed. Producing a resource takes 00 seconds, building a building takes 11 second, and multiple resources can be produced or buildings built at the same time. The maximum number of kinds of resources each building requires and can produce is the smaller of NN and 3030 (= min(N,30)\text{min}(N, 30)).

Brave Cookie wonders which buildings can be constructed within a given time using the buildings that are already built, and wants to know quickly. But Brave Cookie is too busy to figure it out. Let us help my friend Brave Cookie right away. A building that is already built also counts as a building that can be constructed within the given time.

Input

The first line gives the number of kinds of resources NN, the number of buildings already built MM, and the time limit TT. The number of kinds of buildings equals the number of kinds of resources, NN. Both buildings and resources are numbered from 11 to NN.

  • 1≤N≤100,0001 \leq N \leq 100,000
  • 1≤M≤N1 \leq M \leq N
  • 0≤T≤N0 \leq T \leq N

The second line gives MM distinct numbers, which are the numbers of the buildings already built.

Then NN lines follow, each giving a building's number of producible resource kinds and those resource numbers, separated by spaces.

After that, N−MN - M lines follow, each giving the number of a building not yet built, the number of resource kinds that building requires, and those resource numbers, separated by spaces.

Here, the number of resources each building produces and the number of resource kinds required to build a building is at least 11.

The maximum number of kinds of resources each building requires and can produce does not exceed NN and 3030, that is, it is at most min(N,30)\text{min}(N, 30).

Output

On the first line, print the number of buildings that can be built within TT seconds. On the second line, print the numbers of all buildings that can be built within the time limit in ascending order, separated by spaces.

Examples1

  1. Example 1

    Input
    6 2 2
1 3
1 1
1 2
1 3
1 4
1 5
1 6
2 2 1 3
4 3 2 3 5
5 3 1 2 6
6 2 4 5
    Expected output
    3
1 2 3