部活動調査

A 高校の生徒会長である明は、A 高校の生徒がどの部活動に所属しているかを調査することにした。A高校には 1 から N の番号が付けられた N 人の生徒と、1 から M の番号が付けられた M 種類の部活動がある。各部活動に人数制限はなく、0 人の部活動もありえる。ただし、A 高校の校則では生徒はひとつの部活動までしか所属できない。生徒は全員この校則を守っている。

明は生徒会員に調査を依頼し、各行が次のいずれかであるような K 行の記録を入手した。

• 生徒 a と生徒 b は同じ部活動に所属している。
• 生徒 c は部活動 x に所属している。

しかし、この記録には誰かが校則違反になってしまうような矛盾があるかもしれない。明は１行目から順に見ていき、矛盾があると判断できる最初の行を探すことにした。

K 行の記録が与えられたとき、矛盾があると判断できる最初の行の番号を求めるプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N M K
record1
record2
:
recordK

１行目に生徒の人数 N (1 ≤ N ≤ 100000)、部活動の種類の数 M (1 ≤ M ≤ 100000)、記録の行数 K (1 ≤ K ≤ 200000) が与えられる。続く K 行に記録の各行 record_i が、以下のいずれかの形式で与えられる。

1 a b

または

2 c x

先頭の数字が「1」のとき、生徒 a (1 ≤ a ≤ N) と生徒 b (1 ≤ b ≤ N) が同じ部活動に所属していることを示す。ただし、a ≠ b である。

先頭の数字が「2」のとき、生徒 c (1 ≤ c ≤ N) が部活動 x (1 ≤ x ≤ M) に所属していることを示す。

Output

矛盾があると判断できる最初の行の番号を１行に出力する。見つからない場合は 0 を１行に出力する。

Sample Input 1

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

Sample Output 1

4

Sample Input 2

3 2 4
1 1 2
2 1 1
2 3 2
2 2 1

Sample Output 2

0

Sample Input 3

3 2 2
1 1 2
2 1 1

Sample Output 3

0

---