技术团队正在为 PacNW 区域赛做准备！有 $n$ 台计算机需要连接在一起，且与外部互联网隔离。现有 $m$ 条计算机之间的双向连接，每条连接需要 $k$ 种不同线缆中的一种（例如 CAT5、RS232、MIDI 等）。使用所有可能的线缆类型，每台计算机都可以通过某组线缆到达其他任何一台计算机。此外，每对计算机之间最多参与一条连接。最后，为了最大限度地减少泄漏，任意两个不同的简单环路（simple cycle）最多只能有一个公共计算机（简单环路是指每台计算机最多出现一次的环路，如果两个环路至少有一条连接不同，则它们是不同的）。

技术团队需要确保每台计算机都能与所有其他计算机通信，但他们不想在不必使用所有线缆类型的情况下使用它们。你能帮他们找出以下两个问题的答案吗：连接所有计算机所需的最少线缆类型数量是多少，以及有多少种线缆类型的子集能够使每台计算机都能与所有其他计算机通信？

输入格式

第一行包含三个整数 $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$（保证是线缆类型之一）。

输出格式

输出两行，每行包含一个整数。第一行应包含技术团队连接所有计算机所需的最少线缆类型数量。第二行应包含能够使所有计算机相互通信的线缆类型子集的数量。

样例

样例输入 1

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

样例输出 1

2
4