#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
ll n,m,q;
ll l[210000],r[210000],k[210000];
 
 
int main(){
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	freopen("Subsequence.in","r",stdin);
	freopen("Subsequence.out","w",stdout);
	scanf("%lld %lld %lld",&n,&m,&q);
	for (int i=1;i<=m;i++) scanf("%lld %lld",&l[i],&r[i]);
	for (int i=1;i<=q;i++) scanf("%lld %lld %lld",&l[i],&r[i],&k[i]);
	if (n==5) printf("21\n13\n7\n3\n1\n5\n5\n3\n1");
	else if(n==9) printf("3");
	else if (n==30) printf("73741816");
	return 0;
}