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 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
The road names will consist of at most lowercase English letters.
Subtask 1 [50%]
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 .
The next lines contain the intersections, where the line contains string , the name of the known road, and string , 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 north-south roads (martingrove, lloydmanor, and kipling) and a total of east-west roads (winterton and eglinton).
Comments