B - Perfect Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の人が、M 問からなるプログラミングコンテストに参加しました。
参加者は人 1, 人 2, \ldots, 人 N と番号づけられており、問題は問題 1, 問題 2, \ldots, 問題 M と番号づけられています。

このコンテストでは K 個のイベントが順番に起き、i 番目 (1\leq i\leq K) のイベントでは次のことが起きました。

  • 人 A_i が問題 B_i に正解した。

同じイベントが 2 回以上起きることはありません。 また、この 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
  • 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



すべての問題に正解した人がいない場合は、何も出力しないでください。






Score : 200 points







Problem Statement
N people participated in a programming contest consisting of M problems.

The participants are numbered person 1, person 2, \ldots, person N, and the problems are numbered problem 1, problem 2, \ldots, problem M.


In this contest, K events occurred in order; in the i-th event (1\leq i\leq K), the following happened:


    

  • Person A_i solved problem B_i.
    • 



The same event does not occur two or more times.
Also, apart from these K events, nobody solves any problem.


Output the numbers of all people who solved all problems.

If there are multiple such people, output them in ascending order of the time at which they solved all problems.











Constraints
    

  • 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 then (A_i,B_i)\neq (A_j,B_j).
    • 

  • All input values are integers.
    • 
















Input
The input is given from Standard Input in the following format:


N M K
A_1 B_1
A_2 B_2
\vdots
A_K B_K












Output
Output, on one line and separated by spaces, the numbers of all people who solved all problems, in ascending order of the time at which they solved all problems.
If there is no person who solved all problems, output nothing.















Sample Input 1
3 2 5
1 1
3 2
2 1
3 1
1 2












Sample Output 1
3 1



In the contest, the following happened in order.


    

  • Person 1 solved problem 1. So far, person 1 has solved only problem 1.
    • 

  • Person 3 solved problem 2. So far, person 3 has solved only problem 2.
    • 

  • Person 2 solved problem 1. So far, person 2 has solved only problem 1.
    • 

  • Person 3 solved problem 1. So far, person 3 has solved problems 1,2. Thus, at this point person 3 has solved all problems.
    • 

  • Person 1 solved problem 2. So far, person 1 has solved problems 1,2. Thus, at this point person 1 has solved all problems.
    • 



Thus, the people who solved all problems are persons 1,3, and the one who solved all problems earlier is person 3.
Thus, output 3,1 in this order, separated by spaces.













Sample Input 2
2 2 2
1 1
2 2












Sample Output 2


If there is no person who solved all problems, output nothing.