题目描述

X是一个善于研究的地理学家,X喜欢研究对于图上两点之间有多少条奇数路径或偶数路径，今天 L 给了 X 一张 DAG 图，
( DAG 图指有向无环图)，这张图有 N 个点， M 条边。 L 还给出了 Q 个询问，对于每一个询问，给出一个点 Y ， L 想知道从任意点开始，到点 Y 有多少条路径刚好经 过奇数条边，偶数条边。但是由于路径数可能太多，所以只用输出路径数除以 9240606 的余数就可以了。

X被难倒了,于是请来聪明的OIer你，帮他对于每一个询问作出回答。

输入输出格式

输入格式：

输入共 M+Q+2 行。

第一行包含两个整数 N，M 。

第 2~M+1 行，每行两个整数 U,V ，代表 X,Y 之间有一条有向边指向 Y .

第 M+2 行包含一个整数 Q 。

第 M+3~M+Q+2 行，每行一个整数 Y ，询问从到 Y 的所有路径中经过奇数条边的路径数，和偶数条边的路径数。

输出格式：

输出Q行:

对于每一个询问输出一行，两个整数，分别是到 Y 的路径中经过奇数条边的路径数，和经过偶数条边的路径数(除以 9240606 的余数)。

(对于每一个点，从自己走到自己也算一条经过 0 条边的路径)

输入样例1：

6 9
1 4
1 3
1 2
2 3
2 4
3 5
5 6
4 6
4 5
3
3
6
5

输出样例1:

2 2
7 7
4 5

数据范围：

对于30%的数据:N <= 10,M <= 30,Q <= 10。

对于60%的数据:N <= 2000,M <= 4000,Q <= 1000。

对于100%的数据:N <= 50000,M <= 200000,Q <= 50000(此数据下可能有重边，不需特判)。