This page is still under construction.

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

Traffic Planning

Interview

Time limit1sMemory limit128 MB

Summary
Given a directed graph and a start node, list the nodes not reachable from the start by a path of one or more edges; print OK if none.
Level

Medium5 of 10

Topics
Graph, DFS, BFS, Implementation
Solved
No attempts yet

Problem

In a big city like Oslo, most downtown streets are one-way, so changing the traffic pattern is hard. Traffic manager Joan reviews proposals for modifying the traffic pattern, but she has trouble understanding the overall effect of such changes. She is afraid that one day she will approve a proposal that leaves some street with no access at all.

Write a program to help Joan avoid disaster. It reads the streets and their connections and then decides whether every street is accessible from a given starting street.

A street is accessible if it can be reached from the starting street by following one or more one-way connections. In particular, the starting street itself is accessible only if some sequence of connections leads back to it (that is, it lies on a directed cycle reachable from the start).

Input

The input begins with a description of the new traffic system. Each line describes one street and starts with the unique number identifying it. (For convenience, the streets are numbered sequentially 1,2,3,…1, 2, 3, \ldots.) The number is followed by the street name in double quotes, and then by the streets you can reach directly from this street: first a count nn, then the identification numbers r1,r2,…,rnr_1, r_2, \ldots, r_n of those streets. All items describing a street are separated by single spaces.

After the last street line comes a line containing only −1-1. The line after that contains the number of the starting street.

There is no fixed upper bound on the number of streets; the only limit is the size of the computer's main memory. You may assume that no street name is longer than 30 characters.

Output

Print the names of the streets that cannot be reached from the specified starting street, one per line, in the same order in which they were read from the input. If every street is accessible, print OK instead.

Examples3

  1. Example 1

    Input
    1 "Nordstrandveien" 1 5
    2 "Munkerudveien" 0
    3 "Oberst Rodes vei" 1 4
    4 "Jordbærveien" 1 5
    5 "Nordsetergrenda" 0
    6 "Nordseter terasse" 0
    -1
    4
    
    Expected output
    Nordstrandveien
    Munkerudveien
    Oberst Rodes vei
    Jordbærveien
    Nordseter terasse
    
  2. Example 2

    Input
    1 "A" 1 2
    2 "B" 1 3
    3 "C" 1 1
    -1
    1
    
    Expected output
    OK
    
  3. Example 3

    Input
    1 "Alpha" 0
    2 "Beta" 0
    -1
    1
    
    Expected output
    Alpha
    Beta