eolymp
Змагання

Dynamic programming on Trees - Top Level

Дерево

Задано дерево. Для кожної вершини дерева є набір елементів, які можна поміщати в цю вершину. Кожен елемент має вагу – деяке ціле число. Для кожного ребра дерева визначено відношення між вершинами, а саме, відомо, у якій з двох вершин повинен бути елемент з меншою вагою. Потрібно визначити кількість різних способів розташування у вершинах дерева по одному елементу такого, щоб для всіх ребер виконувались відношення. Різні елементи з набору однієї вершини можуть мати однакову вагу.

Вхідні дані

У першому рядку задано кількість вершин n (1n1000) у дереві. Далі йдуть n рядків, в i-му рядку задано список допустимих елементів у вершині i. Рядок починається з цілого числа k (1k1000) – кількості елементів. Слідом записано k цілих чисел wj (1wj109) – ваги елементів.

Далі вхідні дані містять n1 рядок, у кожному з яких записані два різних цілих числа a, b (1a, bn), які означають, що в дереві є ребро між вершинами a та b, і у вершині a повинен бути розміщений елемент меншої ваги, ніж у вершині b.

Вихідні дані

Вивести кількість способів за модулем 1000000007.

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
4
5 1 2 3 4 5
3 2 3 6
2 3 5
1 2
1 2
1 3
4 2
Вихідні дані #1
10
Автор О. Міланін
Джерело ACM, Ukraine, First Stage, 09.04.2011