0379. Фермерское чтиво

Имя входного файла: tree.in
Имя выходного файла: tree.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

Егор – очень почетный фермер. Довольные покупатели прозвали его <<Пышный>>. Секрет его успеха, конечно же лежит в его манере управлять фермой. Например, у него организована строгая иерархия среди всего скота.

Более конкретно, всего в подчинении Егора находится N - 1 скотина с номерами от 2 до N, Егор не любит отбиваться от коллектива, поэтому тоже имеет номер -- 1. У каждой скотины есть непосредственный начальник, причем ровно один. Начальником может быть либо другая скотина, либо сам Егор.

Недавно Егор решил постричь тех скотин, у которых нет подчиненных. Для начала ему нужно составить порядок в котором он будет их стричь. Однако, появилось некоторое затруднение. Чтобы никого не обидеть, Егор должен учесть M требований вида: скотина, которую Егор будет стричь ai-м по счету, должна находиться в подчинении (не обязательно прямом) скотины с номером bi (при этом в требовании bi может оказаться номер скотины без подчиненных, это значит, что именно эту скотину нужно стричь ai-й по счету).

Теперь Егору интересно, сколько существует различных способов постричь скот, удовлетворив всем требованиям. Два способа считаются различными, если порядок стрижки отличается хотя бы в одном номере. Поскольку ответ может быть очень большим, выведите результат по модулю 109 + 7.

Формат входного файла

Первая строка входного файла содержит два целых числа N и M (2 ≤ N ≤ 3 *105, 0 ≤ M ≤ 3 *105) – количество скотин и количество требований, соответственно. Скотина с номером 1 – Егор. В каждой i-й строке из последующих N - 1 строк находится единственное число 1 ≤ pi < i + 1 – начальник скотины с номером i + 1. В каждой i-й строке из последующих M строк находится по два числа 1 ≤ ai, bi ≤ 3 *105 – скотина, которую будут стричь ai-й, должна находится в подчинении (не обязательно прямом) скотины с номером bi. Гарантируется, что ai не превосходит количества скотин без подчиненных. Также номер bi может принадлежать скотине без подчиненных, это означает, что эту скотину нужно стричь ai-й по счету.

Формат выходного файла

В выходной файл выведите единственное число – количество различных способов стрижки по модулю 109 + 7.

Пример:

tree.intree.out
5 3 1 1 2 2 1 2 2 1 3 2 2
6 1 1 1 2 2 2 4 3 6

В первом примере требуется постричь скотин с номерами 3, 4 и 5. При этом скотины 4 и 5 находятся в подчинении у скотины номер 2 и при этом все скотины прямо или косвенно подчиняются Егору. Требования говорят, что в первую и третью очередь нужно стричь подчиненных номера 2. Таким образом мы можем либо в первую очередь стричь четвёртого, в третью пятого, либо наоборот. Третьего же остаётся стричь только во вторую очередь. Таким образом получаем два возможных порядка стрижки: 4 3 5 и 5 3 4.


Источник: Открытый весенний чемпионат ПетрГУ по программированию, 20 апреля 2014

Обсудить       Отправить решение



Версия для печати