Problem: 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 1 to N and M types of club activities numbered 1 to M. There is no limit to the number of people in each club activity, and there can be 0 club activities. 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 student members to investigate and obtained records for line K, such as each line being one of the following:

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



However, there may be a contradiction in this record that would cause someone to violate school rules. Akira decided to look at the first line in order and look for the first line that could be judged to be inconsistent.

Create a program that finds the number of the first line that can be determined to be inconsistent given a record of K lines.



Input

The input is given in the following format.


NMK
record1
record2
::
recordK


The first line gives the number of students N (1 ≤ N ≤ 100000), the number of club activity types M (1 ≤ M ≤ 100000), and the number of recorded lines K (1 ≤ K ≤ 200000). Each line of record, recordi, is given in the following K lines in one of the following formats:


1 a b


Or


2 c x


When the first digit is "1", it indicates that student a (1 ≤ a ≤ N) and student b (1 ≤ b ≤ N) belong to the same club activity. However, a ≠ b.

When the first digit is "2", it indicates that student c (1 ≤ c ≤ N) belongs to club activity x (1 ≤ x ≤ M).

Output

Output the number of the first line that can be determined to be inconsistent on one line. If not found, output 0 on one line.

Examples

Input

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


Output

4


Input

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


Output

0


Input

3 2 2
1 1 2
2 1 1


Output

0

Solution (in CPP):

Solution:
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourd; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, t, s, p, q, last, cnt, sum, ans, dp[2000][2000], a[60000], b[60000];
string str, ss;
bool f[210000];
char c;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
struct Edge { LL to, cost; };
vector<Edge>vec[200000];
vector<LL>v;
map<LL, LL>ma;
multiset<LL>st;

void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
struct QuickFind {
	vector<int> gi; //親
	vector<int> group;
	vector<vector<int>> vg; //併合した後削除する
	vector<vector<int>> tg; //併合した後削除しない
	int n;

	QuickFind(int size) : n(size) {
		gi.resize(n);
		group.resize(n);
		vg.resize(n);
		tg.resize(n);
		for (int i = 0; i < n; i++) {
			gi[i] = i;
			vg[i].push_back(i);
			tg[i].push_back(i);
		}
	}
	bool same_group(int a, int b) {
		return gi[a] == gi[b];
	}
	bool merge(int a, int b) {
		int ga = gi[a];
		int gb = gi[b];
		if (ga == gb) return 1;
		if (vg[ga].size() < vg[gb].size()) swap(ga, gb);
		if (group[ga] != 0 && group[gb] != 0 && group[ga] != group[gb]) {
			return 0;
		}
		group[ga] = max(group[ga], group[gb]);
		group[gb] = max(group[ga], group[gb]);
		for (int j : vg[gb]) gi[j] = ga;
		vg[ga].insert(vg[ga].end(), vg[gb].begin(), vg[gb].end());
		vg[gb].clear();
		tg[ga].insert(tg[ga].end(), tg[gb].begin(), tg[gb].end());
		return 1;
	}
	bool give_group(int i,int k) {
		if (group[gi[i]] != k&&group[gi[i]]!=0)
			return 0;
		group[gi[i]] = k;
		return 1;
	}
};
QuickFind qf(200000);
int main() {
	cin >> n >> m >> k;
	rep(i, k) {
		LL x, y, z;
		cin >> x;
		if (x == 1) {
			cin >> y >> z;
			if (!qf.merge(y, z)) {
				cout << i + 1 << endl;
				return 0;
			}
		}
		if (x == 2) {
			cin >> y >> z;
			if (!qf.give_group(y, z)) {
				cout << i + 1 << endl;
				return 0;
			}
		}
	}
	cout << 0 << endl;
	return 0;
}