#1742. [语言月赛 202508] 共享航班

[语言月赛 202508] 共享航班

题目描述

扶苏获取了 nn 条航线数据,每条数据都是一个字符串,包括一趟航班的代码、出发地、目的地、起飞时间。一条数据的格式是:

CODE-DEP-DES-HH:MM

其中:

  • CODE 是该航班的代码,该代码是一个长度为 66 的字符串,前两位是字母,表示所属航司,后四位是数字,是航司给该航班的代号。同一航司的代码前两位相同,不同航司的代码前两位不同,因此可以用航班号前两位来区分和表示航司。例如 CA1234,SC9876。
  • DEP 是一个长度为 33 的字符串,表示飞机的出发机场代码。不同机场的代码不同,例如 PEK 表示北京首都国际机场。
  • DES 是一个长度为 33 的字符串,表示飞机的到达机场代码。不同机场的代码不同,例如 PVG 表示上海浦东国际机场。
  • HH:MM 是一个长度为 55 的字符串,H 和 M 均是 0∼90 \sim 9 的数字,表示起飞的小时和分钟,不足两位时补 0。例如:09:21 表示 99 点 2121 分。

下面是一个例子:

CA1501-PEK-PVG-08:30
SC5306-PEK-PVG-08:30
ZH2468-PEK-PVG-08:30
CZ1357-PEK-PVG-08:30
MU9197-SHA-TFU-08:00

依次表示:

  • CA 公司售卖的代号为 CA1501 的航班,从 PEK 飞往 PVG,起飞时间 08:30。
  • SC 公司售卖的代号为 SC5306 的航班,从 PEK 飞往 PVG,起飞时间 08:30。
  • ZH 公司售卖的代号为 ZH2468 的航班,从 PEK 飞往 PVG,起飞时间 08:30。
  • CZ 公司售卖的代号为 CZ1357 的航班,从 PEK 飞往 PVG,起飞时间 08:30。
  • MU 公司售卖的代号为 MU9197 的航班,从 SHA 飞往 TFU,起飞时间 08:00。

同时,扶苏还知道有些航司之间有联盟关系,每个航司最多属于一个联盟。两条数据是共享航班当且仅当:

  • 它们的公司属于同一个联盟。
  • 它们起飞、降落机场分别相同。
  • 它们起飞时间相同。

可能有多个航班两两之间均构成代码共享关系,此时它们对应同一趟实际航班。

例如,扶苏知道 CA 和 SC 和 ZH 同属于一个联盟,而 CZ 不属于该联盟,所以上面例子里前三条是共享航班,对应同一趟实际的航班,但前三条和第四条不是共享航班。而第五条和前四条信息的起降地、时间均不同,因此也不和前四条构成代码共享关系。上面例子中共有三趟实际的航班。

已知共有 mm 个联盟,属于第 ii 个联盟的航司有 cic_i 个,其代码(航班号前缀)分别是 si,1,si,2,…sm,cis_{i,1}, s_{i,2}, \dots s_{m, c_i}。同时给定 nn 条航班信息,你要求出这 nn 条信息对应了多少实际的航班。

注意:

  1. 可能有航司不属于任何联盟。
  2. 同一航司在同一时间、同一起降地可能有多条航线数据,此时它们对应同一趟实际航班。

输入格式

第一行是两个整数,表示信息数 nn 和联盟数 mm。

接下来 mm 行,表示一个联盟的信息,按如下格式输入:

  • 首先是一个整数,表示该联盟的航司数 cic_i。
  • 接下来有 cic_i 个长度为 22 的字符串,表示该联盟每个航司的代码(航班号前缀)。

接下来 nn 行,每行一个字符串,表示一条航班信息,其具体格式见【题目描述】部分。

输出格式

输出一行一个整数,表示共有多少个实际航班。

样例

7 2
3 CA ZH SC
2 CZ MF
CA1501-PEK-PVG-08:30
CZ1357-PEK-PVG-08:30
SC5306-PEK-PVG-08:30
ZH2468-PEK-PVG-08:30
MF1357-PEK-PVG-08:30
MU9197-SHA-TFU-08:00
CA9197-SHA-TFU-08:00
4

题目来源:洛谷 B4388