008 - 部活動調査

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

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

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

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

課題

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

入力

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

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)に所属していることを示す。

時間制限

入力に対して、実行時間が３秒を超えてはならない。

出力

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

入出力例

入力例１

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

出力例１

4

入力例２

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

出力例２

0

入力例３

3 2 2
1 1 2
2 1 1

出力例３

0