This page is still under construction.

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

Claire and Potions

Time limit1sMemory limit256 MB

Summary
Given recipes that combine several potions into another, and an initial set of owned potions, find every potion that can be produced.
Level

Medium5 of 10

Topics
Graph, Topological sort, Queue, Hash map
Solved
No attempts yet

Problem

There are N kinds of potions in the world, and Claire knows M recipes.

A recipe can be written as (x1, x2, ..., xk) → r, which means potions x1, x2, ..., xk can be mixed together to make potion r.

Claire currently has only potions y1, y2, ..., yL. Find every potion she can make.

Assume Claire has an unlimited amount of each kind of potion she owns.

Input

The first line gives the number of kinds of potions in the world N (3 ≤ N ≤ 200,000) and the number of recipes Claire knows M (1 ≤ M ≤ 200,000).

Each of the next M lines gives the information for one recipe: ki, xi1, xi2, ..., xiki, ri (1 ≤ ki < N, 1 ≤ xij, ri ≤ N, xij ≠ ri). This means the recipe (xi1, xi2, ..., xiki) → ri.

Line M+2 gives the number of kinds of potions Claire currently has, L (1 ≤ L < N).

Line M+3 gives y1, y2, ..., yL (1 ≤ yi ≤ N).

The sum of all ki does not exceed 400,000.

Output

On the first line, print the number of potions Claire can make.

On the second line, print the numbers of the potions she can make in increasing order.

Examples2

  1. Example 1

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

  2. Example 2

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