Time Limit : sec, Memory Limit : KB
English / Japanese  

Investigation of Club Activities

Akira, the student council president of A High School, decided to investigate which club activities the A High School students belong to. A High School has N students numbered from 1 to N and M types of club activities numbered from 1 to M . There is no limit to the number of students in each club, and it is possible to have zero students in a club. However, according to the school rules of A High School, students can only belong to one club activity. All students follow this school rule.

Akira asked a student member to do some research and obtained a record of K lines such that each line is one of the following.

  • Student a and student b belong to the same club activity.
  • Student c belongs to club activity x .

However, there may be discrepancies in this record that would cause someone to violate the school rules. Akira decided to look at it from the first line and look for the first line where he could determine that there was a discrepancy.

Write a program to find the number of the first line that can be determined to be inconsistent from the given the record of K lines.

Input

Input is given in the following format.

N M K
record1
record2
:
recordK

In the first line, the number of students N (1 ≤ N ≤ 100000), the number of types of club activities M (1 ≤ M ≤ 100000), and the number of lines recorded K (1 ≤ K ≤ 200000) are given. Each record i of the record is given in the following K line in one of the following formats:

1 a b

or

2 c x

When the first number is "1", student a (1 ≤ a N ) and student b (1 ≤ b N ) belongs to the same club activity. Note that a b .

When the first number is "2", the student c (1 ≤ c N ) is in the club activity x (1 ≤ x M ).

Output

Output the number of the first line that can be determined to be inconsistent in a single line. If none is found, output 0 in a single line.

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