002 - 部活動調査

時間制限 2 秒 / メモリ制限 256 MB / 得点 10 / x 4 /


TLE
2sec
MLE
256MB
得点
10

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

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

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

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

課題

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

入力

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

N M K
record1
record2
:
recordK

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

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

時間制限

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

出力

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

入出力例

入力例1

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

出力例1

4

入力例2

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

出力例2

0

入力例3

3 2 2
1 1 2
2 1 1

出力例3

0