#P41. [KBC002Ex] Gods

[KBC002Ex] Gods

题目背景

在这个神奇的世界,有 mm 种宗教和 kk 位神。每个人只能信仰一种宗教,但一种宗教可以有很多教徒。 一位神能出现在很多宗教里,一种宗教也能出现很多位神。一个人只要信仰了某种宗教, 就会信仰该宗教出现的所有神。小明是一个神学家,他想知道最受欢迎的神是谁,但他数学不太好,所以请你来帮他。

题目描述

根据人口普查的结果,这个世界一共有 nn 个人(小明除外),不存在无神论者,每个人都信仰一种宗教。小明会给你提供他设置的宗教调查问卷(每个人都参加了)的结果,以及他通过查阅资料整理出的每种宗教出现过的神的情况,请你帮他求出信仰人数最多的神。

输入格式

第一行,三个数 nn, mm, kk

接下来 nn 行,每行一个数,代表这个人信仰的宗教。

最后 mm 行,每行第一个数 ss 代表这种宗教出现过的神的数量。然后 ss 个数是这种宗教出现过的神。

输出格式

一行,最受欢迎的神,如果有信仰人数相同的,就输出编号小的。

5 2 3
1
1
2
2
1
2 1 2
2 1 3
1
10 3 5
1
2
3
2
1
2
1
2
3
1
3 1 3 5
2 2 4
2 3 4
3

提示

1n1000001 \leq n \leq 100000

1m1001 \leq m \leq 100

1s<k100001 \leq s < k \leq 10000

后记

在你的帮助下,小明发现最受欢迎的神竟然是 nr0728\color{#e74c3c}\mathsf{nr0728} ,他还查到了一些看似无管紧要的事情:

1、毁灭之神 _s_z_y_\color{#e74c3c}\mathsf{\_s\_z\_y\_} 在黑暗之神 klyj1\color{#e67e22}\mathsf{klyj1} 对摸鱼快乐大肆破坏时趁火打劫、助纣为虐,老奸巨猾,罪大恶极!!!他跑得很快,每秒能跑 hh

2、在逻辑迷宫的中央有这样一座 nr0728\color{#e74c3c}\mathsf{nr0728} 的雕像,叫智慧神像,神像下面还埋着一个宝箱,里面有逻辑迷宫的地图,但是需要密码才能打开。

3、死神 lyw987654321\color{#BFBFBF}\mathsf{lyw987654321} 曾今是个 摸鱼快乐 的人类,没人知道他是怎么死的,人们只知道他是在大灾变前死的。他死后成了死神,管理着 他的墓地,时刻盼望着复活。

小明并没有太在意这些事情,但他没想到......

预知后事如何,请看下回分解。