← 返回题目列表

AtCoder · abc424_b

D. 完美

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

N 人们参加了一场编程竞赛,其中包括 M 问题。
参加者编号为人 1, 人 2, \ldots, 人 N,并且问题已编号问题 1,问题 2, \ldots,问题 M.

在本次比赛中, K 事件按顺序发生;在 i第一个事件 (1\leq i\leq K),发生了以下情况:

  • 人 A_i 已解决问题 B_i.

同一事件不会发生两次或多次。 另外,除了这些 K 事件,没有人解决任何问题。

输出解决所有问题的所有人的数量。
如果这样的人有多个,则按照解决所有问题的时间从小到大的顺序输出。

约束

  • 1 \leq N \leq 10
  • 1 \leq M \leq 10
  • K \geq 1
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq M
  • If i\neq j 然后 (A_i,B_i)\neq (A_j,B_j).
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M K
A_1 B_1
A_2 B_2
\vdots
A_K B_K

输出

在一行上输出解决所有问题的所有人的数量,并按解决所有问题的时间升序排列,并用空格分隔。 如果没有人解决所有问题,就什么也不输出。


示例输入 1

3 2 5
1 1
3 2
2 1
3 1
1 2

示例输出 1

3 1

在比赛中,按顺序发生了以下事情。

  • 人 1 已解决问题 1。到目前为止,人 1 解决了唯一的问题 1.
  • 人 3 已解决问题 2。到目前为止,人 3 解决了唯一的问题 2.
  • 人 2 已解决问题 1。到目前为止,人 2 解决了唯一的问题 1.
  • 人 3 已解决问题 1。到目前为止,人 3 已解决问题 1,2。因此,此时人 3 已解决所有问题。
  • 人 1 已解决问题 2。到目前为止,人 1 已解决问题 1,2。因此,此时人 1 已解决所有问题。

因此,解决所有问题的人是人 1,3,而最先解决所有问题的是人 3。 因此,输出 3,1 按此顺序,用空格分隔。


示例输入 2

2 2 2
1 1
2 2

示例输出 2


如果没有人解决所有问题,则不输出任何内容。