eolymp
bolt
Try our new interface for solving problems
Problems

Приготовление десертов

Приготовление десертов

Приготовление десертов можно считать ремеслом, можно считать искусством, а можно считать и наукой. В этой задаче мы будем использовать третий из указанных подходов. Одна из кофеен предлагает своим посетителям большой выбор десертов, каждый из которых состоит из кусочка пирога с начинкой, который сверху украшен шариком мороженого. При этом тесто пирога может быть приготовлено одним из \textbf{n} способов, существует \textbf{m} вариантов начинки и \textbf{k} сортов мороженого. К сожалению, не все типы теста сочетаются со всем начинками, не все начинки --- со всеми сортами мороженого, и не все сорта мороженого --- со всеми типами теста. Ваша задача состоит в определении числа типов десертов, которые могут быть приготовлены так, чтобы все три ингредиента сочетались друг с другом. \InputFile Первая строка содержит три целых числа: \textbf{n}, \textbf{m} и \textbf{k} (\textbf{1} ≤ \textbf{n}, \textbf{m}, \textbf{k} ≤ \textbf{50}). Вторая строка содержит одно целое число \textbf{p} (\textbf{0} ≤ \textbf{p} ≤ \textbf{200}) --- количество пар типов теста и начинок, не сочетающихся друг с другом. Каждая из последующих \textbf{p} строк содержит по два целых числа \textbf{a} и \textbf{b} (\textbf{1} ≤ \textbf{a} ≤ \textbf{n}, \textbf{1} ≤ \textbf{b} ≤ \textbf{m}) --- номера типа теста и начинки, которые не сочетаются друг с другом. Никакая пара несочетающихся типов теста и начинки не указана более одного раза. Следующая строка содержит одно целое число \textbf{q} (\textbf{0} ≤ \textbf{q} ≤ \textbf{200}) --- количество пар начинок и сортов мороженого, не сочетающихся друг с другом. Каждая из последующих \textbf{q} строк содержит по два целых числа \textbf{a} и \textbf{b} (\textbf{1} ≤ \textbf{a} ≤ \textbf{m}, \textbf{1} ≤ \textbf{b} ≤ \textbf{k}) --- номера начинки и сорта мороженого, которые не сочетаются друг с другом. Никакая пара несочетающихся начинки и сорта мороженого не указана более одного раза. Следующая строка содержит одно целое число \textbf{r} (\textbf{0} ≤ \textbf{r} ≤ \textbf{200}) --- количество пар типов теста и сортов мороженого, не сочетающихся друг с другом. Каждая из последующих \textbf{r} строк содержит по два целых числа \textbf{a} и \textbf{b} (\textbf{1} ≤ \textbf{a} ≤ \textbf{n}, \textbf{1} ≤ \textbf{b} ≤ \textbf{k}) --- номера типа теста и сорта мороженого, которые не сочетаются друг с другом. Никакая пара несочетающихся типа теста и сорта мороженого не указана более одного раза. \OutputFile Выведите одно число --- число типов десертов, которые могут быть приготовлены так, чтобы все три ингредиента сочетались друг с другом.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
2 1 2
1
2 1
1
1 2
1
2 2
Output example #1
1
Source Russian-Code-Cup-2011 2-й кв. раунд