컴퓨터 연결하기

시간 제한은 3000 ms, 메모리 제한은 2048 MB이다. 대회를 위해 기술팀이 PacNW 지역 대회를 준비하고 있다. 기술팀은 외부 인터넷과 분리된 상태로 컴퓨터 $n$대를 연결해야 한다. 컴퓨터 사이에는 양방향 연결이 $m$개 있고, 각 연결에는 $k$종류의 케이블 중 하나가 필요하다(예: CAT5, RS232, MIDI 등). 가능한 모든 케이블 종류를 사용하면, 케이블의 일부 집합을 따라 모든 컴퓨터가 서로 도달할 수 있다. 두 컴퓨터의 쌍은 최대 하나의 연결만 가진다. 누출을 최소화하기 위해, 서로 다른 두 단순 사이클은 공통 컴퓨터를 둘 이상 가질 수 없다. 단순 사이클은 각 컴퓨터가 최대 한 번만 등장하는 사이클이며, 한 사이클에만 있는 연결이 하나라도 있으면 두 사이클은 서로 다른 사이클이다.

첫 줄에 정수 세 개 $n$, $m$, $k$가 주어진다($1\le n\le 2\cdot 10^5$, $n - 1\le m\le 3\cdot 10^5$, $1\le k\le 24$). 각각 컴퓨터 수, 연결 수, 케이블 종류 수이다. 다음 줄에는 $k$개의 문자열이 주어지며, $i$번째 문자열은 $i$번째 케이블 종류의 이름이다. 케이블 이름은 1자 이상 10자 이하의 영숫자로 이루어지며, 모든 이름은 서로 다르다. 다음 $m$개의 줄은 연결을 나타낸다. $i$번째 줄에는 정수 두 개 $x$, $y$($1\le x < y\le n$)와 케이블 종류 중 하나인 문자열 $s$가 주어진다.

정수 한 개씩을 담은 두 줄을 출력한다. 첫 줄에는 모든 컴퓨터를 연결하는 데 필요한 케이블 종류의 최소 개수를 출력한다. 둘째 줄에는 그 종류만 설치했을 때 모든 컴퓨터가 서로 연결되는 케이블 종류 부분집합의 개수를 출력한다.