Dependencies

Amazon Web Services (AWS) CloudFormation is a service that helps you model and set up your AWS resources so that you can spend less time managing those resources and more time focusing on your applications that run in AWS. You create a template that describes all the AWS resources that you want, and CloudFormation takes care of provisioning and configuring those resources for you. In a CloudFormation template, you specify the logical names of resources, together with their properties, including the dependent resources. The logical name (or logical ID) must be alphanumeric and unique within the template. The logical name is used to reference to the resource in other parts of the template.

In the following CloudFormation template, such logical names are MyEC2Instance and MyEIP:

AWSTemplateFormatVersion: 2010-09-09
Description: A sample template
Resources:
  MyEC2Instance:
    Type: 'AWS::EC2::Instance'
    Properties:
      ImageId: ami-0ff8a91507f77f867
      InstanceType: t2.micro
      KeyName: testkey
      BlockDeviceMappings:
        - DeviceName: /dev/sdm
          Ebs:
            VolumeType: io1
            Iops: 200
            DeleteOnTermination: false
            VolumeSize: 20
  MyEIP:
    Type: 'AWS::EC2::EIP'
    Properties:
      InstanceId: !Ref MyEC2Instance

Write a program that reads logical names of resources given in an AWS CloudFormation template from the standard input. For each logical name, you will be given all the other names of resources that are required to exist for the resource to be created. Your program has to determine whether a given sequence of resources can or cannot be created in the specified order, and if not, the program also has to give the logical names of all resources in the sequence that cannot be created.

Input Specification

The first line of the input contains two integers R and S, representing the number of resources and the number of sequences, respectively (1 ≤ R ≤ 100, 1 ≤ S ≤ 100). Each of the following R lines describes a resource and its dependencies (in no particular order). Each resource is represented by an identifier, which is a string of at most 20 alphanumeric characters. The first resource in each line is followed by a colon (“:”), and then optionally a space-separated list of its dependencies, also being resource identifiers. Finally, the last S lines of the input contain the sequences, in the form of space-separated resource IDs. Both the resource descriptions and the sequences will contain only valid resource IDs.

Output Specification

For each sequence in the input, print one line to the output.

If there are at least two resources in the sequence that cannot be created in the given order (“problematic” resources), then print “Problematic resources: ”, followed by a space-separated list of the logical names of all the problematic resources in the same order as they appeared in the sequence.

If there is only one problematic resource, print the message “Problematic resource: ”, followed by the logical name of the problematic resource.

If all the resources can be created in the order presented in the sequence, then print “No problematic resources.”.

Sample Input 1

1. 2 2
2. MyEC2Instance:
3. MyEIP: MyEC2Instance
4. MyEC2Instance MyEIP
5. MyEIP MyEC2Instance

download as text file

Output for Sample Input 1

1. No problematic resources.
2. Problematic resource: MyEIP

download as text file

Sample Input 2

1. 5 2
2. A: B C D
3. B: D
4. C:
5. D:
6. E: A B
7. A B C D E
8. D B C A E

download as text file

Output for Sample Input 2

1. Problematic resources: A B E
2. No problematic resources.

download as text file