DMOPC '13 Contest 3 P1 - Sharing is Caring

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type

As the name implies, Googol Drive stores a vast amount of documents. So vast, in fact, that it would be impractical to manually search which documents are "shared with you" (and unfortunately, Googol does not support this operation yet). Given a list of N people numbered 1 to N who have an account on Googol Drive and M documents which are shared from person p to person q (1 \le p, q \le N), figure out which documents are "shared with you" — that is, you have direct access to such a document as person q.

Input Specification

The first line of input contains two integers, N and M.

The next M pairs of lines will each contain p_i and q_i on the first line, and the document title on the second line. You can assume that no document title is over 30 characters long.

The last line of input will be one integer Y (1 \le Y \le N), your number.

Output Specification

You are to output all documents that are "shared with you" (shared with person Y). The document names should each have their own line, and document names are case-sensitive. The order in which you output them in does not matter, as long the list is correct as a whole.

Constraints

Test Case BatchMarksTime LimitMemory LimitConstraints
1 [5 cases]401 s16 MiB1 \le N \le 10; 0 \le M \le 10
2 [3 cases]201 s16 MiB1 \le N \le 10; 0 \le M \le 100
3 [3 cases]201 s16 MiB1 \le N \le 1\,000; 0 \le M \le 1\,000
4 [3 cases]201 s16 MiB1 \le N \le 1\,000\,000\,000; 0 \le M \le 10\,000

Sample Input 1

3 3
1 2
Road to Becoming a Philosopher
2 3
Hello, World
3 2
Untitled Document
2

Sample Output 1

Road to Becoming a Philosopher
Untitled Document

Explanation for Sample Input 1

Although all three documents are visible by you, you created the second one. Therefore, only two documents are "shared with you".

Sample Input 2

4 3
1 2
Chapter 15
1 3
Chapter 16
1 4
Chapter 16.5
1

Sample Output 2

(there is no output)

Explanation for Sample Input 2

No documents are "shared with you" — instead, you are the one sharing documents with others.


Comments


  • -2
    tiger2018  commented on Nov. 4, 2017, 10:01 p.m.

    Googol? isn't it supposed to be Google?


  • -2
    AlanL  commented on Oct. 29, 2017, 6:01 p.m. edit 2

    Nvm


  • -3
    Anix55  commented on March 17, 2016, 3:01 p.m.

    does order matter?


    • 0
      AlanL  commented on Oct. 29, 2017, 6:02 p.m.

      Order does not matter, it says so in the question.