SP4988 MOWS - Madrids One Way Streets

PolyProg 希望让洛桑联邦理工学院的顶尖程序员参加在马德里的比赛。一个重要的问题就是在马德里该入住哪里。这个地方不仅要价格实惠，还需要临近比赛地点和主要景区。 麻烦的是，马德里的街道几乎都是单行道（实际上并不是这样，但我们觉得这个问题很有趣，于是把它加入到了比赛里）。我们希望能遵循交通规则，顺利往返比赛地点和酒店……你能帮我们找到一个合适的酒店吗？ 其实，我们的目标是找到一个酒店，从那里可以往返于所有感兴趣的地点。如果做不到，我们就希望找到一个能够往返最多感兴趣地点的酒店。如果有多个酒店能达到相同数量的地点，你应该选择编号最小的酒店。

第一行输入包含四个整数：$N$、$H$、$P$ 和 $S$。为简化问题，我们用数字编号来表示酒店和感兴趣地点：酒店的编号从 $1$ 到 $H$，而感兴趣地点的编号从 $1001$ 到 $1000 + P$。 接下来的 $S$ 行每行有两个整数 $A_s$ 和 $B_s$，表示从 $A_s$ 到 $B_s$ 有一条单向街道。 每个测试用例之前都有一个空行。 以下图展示了与示例输入对应的图形： 

对于每个测试用例，输出一行，包含最佳酒店的编号，及从该酒店可以往返的感兴趣地点的数量。 **本翻译由 AI 自动生成**