복잡한 문제

컴퓨터 과학에는 많은 문제가 있고, 그중 일부는 다른 문제보다 어렵다. 컴퓨터 과학자들은 문제를 복잡도 클래스로 묶고, 이 클래스들이 서로 어떤 관계를 맺는지 분석한다.

복잡도 클래스는 단순히 문제들의 집합이다. 예를 들어 복잡도 클래스 P는 실행 시간이 입력 크기의 다항식 함수인 알고리즘으로 풀 수 있는 결정 문제들의 집합이다. P에 속한 모든 문제는 NP에도 속한다. NP는 "예" 입력을 다항 시간에 검증할 수 있는 결정 문제들의 집합이다. NP의 모든 문제가 P에도 속하는지는 알려져 있지 않으므로, P와 NP는 하나의 클래스일 수도 있고 서로 다른 두 클래스일 수도 있다.

정지 문제는 모든 결정 문제의 집합인 ALL에 속하지만, 튜링 머신으로 풀 수 있는 결정 문제의 집합인 R에는 속하지 않는다. 따라서 ALL과 R은 서로 다른 두 복잡도 클래스다.

복잡도 클래스 사이의 관계가 주어졌을 때, 서로 다른 복잡도 클래스의 최소 개수와 최대 개수를 구하라.

첫째 줄에 공백으로 구분된 두 정수 $0 \leq M, N \leq 10^5$가 주어진다. 단, $M + N > 0$이다.

다음 $M$개의 줄에는 서로 다른 두 복잡도 클래스 $A_i$와 $B_i$가 주어진다. 이는 $A_i \subseteq B_i$를 뜻하며, $A_i$에 속한 모든 문제는 $B_i$에도 속한다.

그다음 $N$개의 줄에는 서로 다른 두 복잡도 클래스 $A_j$와 $B_j$가 주어진다. 이는 $A_j \subsetneq B_j$를 뜻하며, $A_j$에 속한 모든 문제가 $B_j$에도 속하고, $B_j$에는 $A_j$에 속하지 않는 문제가 적어도 하나 있다.

복잡도 클래스는 영문자 1자 이상 8자 이하로 이루어지며, 대문자와 소문자를 모두 쓸 수 있다. 서로 다른 두 클래스 사이의 관계는 최대 하나만 주어지며, 주어진 관계들은 모순되지 않는다.

주어진 관계에 나타나는 서로 다른 복잡도 클래스의 최소 개수와 최대 개수를 공백으로 구분하여 한 줄에 출력한다.