Problem D
Connecting Computers

The tech team is gearing up for the PacNW Regional! There are $n$ computers that need to be connected together for the contest, isolated from the outside internet. There are $m$ bidirectional connections between computers, each connection requiring one of $k$ different types of cable (for example, CAT5, RS232, MIDI, etc.) Using all the possible cable types, every computer is reachable from every other computer by following some set of cables. In addition, each pair of computers participates in at most one connection. Finally, to minimize leakage, no two distinct simple cycles of connected computers can have more than one computer in common (a simple cycle is a cycle where each computer can appear at most once, and two cycles are distinct if there is at least one connection present in one but not the other).

The tech team needs to make sure that every computer can communicate with every other computer, but doesn’t want to use all the cable types if they don’t have to. Can you help them figure out the answers to two questions: what is the minimum number of cable types they need to connect all of the computers, and how many subsets of cable types would allow every computer to communicate with every other computer?

Input

The first line contains three integers $n$, $m$, and $k$ ($1\le n\le 2\cdot 10^5$, $n - 1\le m\le 3\cdot 10^5$, $1\le k\le 24$) — the number of computers, the number of connections, and the number of cable types respectively.

The next line contains $k$ strings: the $i^{\texttt{th}}$ string is the name of the $i^{\texttt{th}}$ cable type. Each cable name is made up of between $1$ and $10$ alphanumeric characters. It is guaranteed that the cable names are distinct.

The next $m$ lines describe the connections between the computers. The $i^{\texttt{th}}$ line contains two integers $x$ and $y$ ($1\le x < y\le n$) and a string $s$ (guaranteed to be one of the cable types).

Output

Output two lines, each containing a single integer. The first line should contain the minimum number of cable types the tech team needs connect all the computers. The second line should contain the number of subsets of cable types such that only installing those types would connect all of the computers.

6 7 4
CAT5 RS232 MIDI USBC
1 2 CAT5
2 3 MIDI
3 4 MIDI
2 4 CAT5
4 5 MIDI
5 6 MIDI
4 6 RS232

2
4