MCIPC Contest 2 P3 - Snowy Streets

View as PDF

Submit solution

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

Authors:
Problem type

Whenever it snows, the Government of Ontario has a very particular solution to clear the roads. A road in Ontario is either east-west or north-south. If a road is east-west, then the company Weast Winter Weather is responsible for clearing that road. Likewise, if a road is north-south then the company Sorth Snow Solutions is responsible for clearing that road.

As Peter is an avid snowplow enthusiast, he wants to know how many roads each company clears. To do this, he decides to wander the streets to figure out how many roads are north-south, and how many are east-west. Peter will start wandering from his home street, which he knows the cardinal direction to. Whenever he encounters a new road at an intersection, where a north-south road and an east-west road intersect, he will mark down the street he is currently on, and then the new road. Over the course of his journey, he notes down N intersections. Peter only stops once he has visited every road at least once.

Note: During Peter's walk he may backtrack on already-known roads. If he encounters an intersection where he has already seen both roads he will not write it down.

Given this information, can you help Peter find out how many roads are north-south, and how many roads are east-west?

Constraints

1 \le N \le 5 \times 10^5

The road names will consist of at most 20 lowercase English letters.

Subtask 1 [50%]

1 \le N \le 10^3

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains two strings space separated: the name of the street Peter starts at, and ns to denote that the street is north-south, or ew to denote that the street is east-west.

The second line contains a single integer N.

The next N lines contain the intersections, where the i^\text{th} line contains string u_i, the name of the known road, and string v_i, the name of the new road that Peter has not seen before, separated by a space.

Output Specification

Output the number of north-south roads, and the number of east-west roads, on the same line separated by a space.

Sample Input

martingrove ns
4
martingrove winterton
martingrove eglinton
winterton lloydmanor
eglinton kipling

Sample Output

3 2

Explanation for Sample

martingrove is given as a north-south road.

martingrove has an intersection with winterton, therefore winterton must be an east-west road.

martingrove has an intersection with eglinton, therefore eglinton must be an east-west road.

winterton has an intersection with lloydmanor, therefore lloydmanor must be a north-south road.

eglinton has an intersection with kipling, therefore kipling must be a north-south road.

There is a total of 3 north-south roads (martingrove, lloydmanor, and kipling) and a total of 2 east-west roads (winterton and eglinton).


Comments

There are no comments at the moment.