시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 2 1 1 100.000%

문제

You are playing a culture simulation game, in which your culture can develop various technologies. Some technologies depend upon others; if technology A depends upon technology B, you cannot develop B until you have developed A. Your culture can work on only one technology at a time.

In the game, you have goals which require particular technologies. You have decided to write a program to help you by planning out the order in which to develop technologies.

입력

The input to your program starts with the number of test cases, T, on a line by itself. T test cases follow. Each one consists of:

  • One line with an integer, M, which is the number of technological dependencies.
  • M lines, each one containing two technology names, separated by a colon (':'). The first technology depends on the second one.
  • One line with an integer, Q, which is the number of goal technologies.
  • Q lines, each naming a goal technology.

Each technology name is a sequence of alphanumeric characters (letters or numbers). Technology names are case-sensitive.

Limits

  • T ≤ 25
  • M ≥ 1
  • Q ≥ 1
  • There will be no cycles in the dependency graph.
  • M ≤ 10
  • Q ≤ 10.

출력

The output for each case should start with a line of the form "Case #CD", where C is the case number, starting from 1, and D is the smallest possible number of technologies that have to be researched. The next D lines should each contain one technology, in the order that they need to be researched.

If there are several possible correct orderings, any one of them is acceptable.

예제 입력 1

4
9
Metalworking:Fire
Pottery:Fire
Iron:Metalworking
Steel:Iron
Battleships:Steel
Alchemy:Fire
Chemistry:Alchemy
Explosives:Chemistry
Battleships:Explosives
1
Battleships
9
Metalworking:Fire
Pottery:Fire
Iron:Metalworking
Steel:Iron
Battleships:Steel
Alchemy:Fire
Chemistry:Alchemy
Explosives:Chemistry
Battleships:Explosives
2
Metalworking
Pottery
2
b:a
c:b
1
d
1
A:a
1
A

예제 출력 1

Case #1: 8
Fire
Metalworking
Iron
Steel
Alchemy
Chemistry
Explosives
Battleships
Case #2: 3
Fire
Pottery
Metalworking
Case #3: 1
d
Case #4: 2
a
A

출처

Contest > Google Code Jam > EuroPython 2012 > EuroPython 2012 D1번

  • 스페셜 저지를 만든 사람: isku

채점

  • 예제는 채점하지 않는다.