2008 Canadian Computing Competition, Day 1

Day 1, Problem 2: King & Weber

It is easy to get lost in Kitchener-Waterloo. Many streets that are mostly parallel actually intersect, sometimes multiple times. The best-known example is King and Weber Streets. Other examples include Westmount and Fischer-Hallman, University and Erb, and Queen and Highland.

Navigation is easier in cities that respect the "Manhattan Assumption": all streets are straight lines in a Euclidean plane, and any two streets are either parallel or perpendicular to each other. Visitors to Manhattan are cautioned that even Manhattan itself does not fully satisfy this assumption.

The input to your program will be a sequence of observations followed by a sequence of queries for a particular city. An observation asserts either that two streets are parallel, or that they intersect. A query asks whether two streets are parallel, or whether they intersect, provided the city satisfies the Manhattan Assumption.

Input

The first line of input contains two integers m and n (1 ≤ m, n ≤ 100000). Each of the following m lines contains an observation. Each observation consists of three words separated by spaces: the two street names, and either the word parallel or the word intersect. Each street name is a sequence of no more than 100 uppercase or lowercase letters. The observations are followed by n queries, each on a separate line. A query consists of two street names separated by a space.

Output

If it is impossible for the city to conform to both the Manhattan Assumption and the specified observations, output a single line containing the word Waterloo. Otherwise, output n lines containing the answers to the n queries. Each answer should be one of the following three words: parallel, intersect, unknown. If the two streets queried are parallel in every city satisfying the given observations and the Manhattan Assumption, the output should be parallel. If they are perpendicular in every such city, the output should be intersect. If they are parallel in some such city and perpendicular in another such city, the output should be unknown.

Sample Input

3 3
fourthstreet fifthstreet parallel
fifthstreet sixthstreet parallel
fourthavenue fifthstreet intersect
sixthstreet fourthstreet
sixthstreet fourthavenue
sixthstreet King

Sample Output

parallel
intersect
unknown

Sample Input 2

2 1
King Weber parallel
King Weber intersect
King Weber

Sample Output 2

Waterloo

Grading

You can assume that 20% of the test cases will have 1 ≤ m, n ≤ 100. All test cases will have 1 ≤ m, n ≤ 100000. Your solution must use at most 512 MB of memory and run in at most 3 seconds.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 3.00s
Memory Limit: 512M
Added: Dec 07, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

http://wcipeg.com/submissions/src/384111
According to the feedback from the judge, all of my WA is because of the wrong output of "Waterloo". Am I understanding when to output Waterloo correctly? I appreciate your help!!!!

so if it turns out in the observed data, a street that should be parallel to another street is perpendicular to it or vice versa, you output Waterloo. so when would I ever have to output unknown?(other than the case where you get a street in the query that doesn't exist in the input)The description says if the two streets are parallel in some such city and perpendicular in another such city, the output should be uknown. what is this thing talking about? What CITIES??! sorry if i'm being stupid...

If I say this:

2 4
HansonRoad BrianAvenue parallel
JacobBoulevard TobyLane intersect
HansonRoad TobyLane

Output:

Unknown

You only know that HansonRoad and BrianAvenue are parallel and that JacobBoulevard and TobyLane intersect.  You do not, however, know anything about HansonRoad and TobyLane.  Therefore, you output unknown.

oooh thanks