2756: 阿迪王

“叮铃铃铃……”闹钟响了，gaosh又得去上学了。由于时间仓促，他随手拿了一件衣服、一条裤子、一双鞋子并套在了身上。正要出门时，gaosh的妈妈阻止了他，因为她认为耐克的裤子配不上阿迪王的衣服（这是当然的吧-_-#）。事实上，gaosh每天都会遇到类似的问题，有一天，他突然想知道他有多少种衣服搭配的方式，你能帮帮他吗？   输入数据：    第1行：三个整数n，m，k<=1000，表示gaosh的衣服总数、裤子总数和鞋子总数。    第2行：一个整数p<=2000000，表示gaosh的妈妈有p个“XX与XX不能搭配”的观念。    第3~p+2行：每行给出一个限制条件，保证只有“clothes x pants y”或“pants y shoes z”两种形式，分别表示“衣服x不能与裤子y搭配”以及“裤子y不能与鞋z搭配”，保证不出现重复的条件。

   一行一个整数表示有多少种满足gaosh妈妈要求的搭配。

2 2 2

0

8

in
2 2 2
1
clothes 1 pants 1

out
6

in
2 2 2
2
clothes 1 pants 1
pants 1 shoes 1

out
5