题目描述

Rikka 偶然发现了一座无名古庙及其内部的地图。这座庙宇包含 $n$ 个彼此分离的房间，若干条有向道路连接着这些房间，构成了一张有向无环图。

当一位访客进入古庙时，她会出现在第一个房间。她可以在第 $n$ 个房间找到古庙的出口。需要注意，从入口出发她可能无法到达所有的房间，同时，从某些内部房间出发，她或许根本没有机会离开古庙。

所有房间都存放着一些宝物。第 $i$ 个房间中宝物的重量为 $w_i$，价值为 $c_i$。当一位访客到达出口时，如果她所取宝物的总重量除以 $k$ 的余数恰好等于 $t$（其中 $k$ 与 $t$ 为预先给定的整数），她才被允许离开古庙。

此外，有一位守卫正站在某个房间中守护宝物，但没有人知道她站在哪个房间。为了避免遭到攻击，访客在任何时候都不应踏入守卫所在的房间。

现在 Rikka 决定造访这座无名古庙。她将选择一条从入口到出口的路径，并拾取她所经过的所有房间中的宝物。她希望你对于每个 $i = 1$ 到 $n$，在假设守卫正站在第 $i$ 个房间的情况下，分别计算她能够获得的最大总价值是多少，以及她有多少种不同的路径方案可以达到这个最大值。

输入格式

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n$（$2 \le n \le 10^5$），表示房间的数量，以及 $m$（$0 \le m \le 2 \times 10^5$），表示有向道路的数量。

接下来的 $n$ 行描述所有房间。其中第 $i$ 行包含两个整数 $w_i$ 和 $c_i$（$1 \le w_i, c_i \le 10^9$）。

再接下来的 $m$ 行描述所有道路。其中第 $i$ 行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示一条从第 $u$ 个房间通往第 $v$ 个房间的有向道路。

最后一行包含两个整数 $k$ 和 $t$（$0 \le t < k \le 100$），表示离开古庙的条件的参数。

输入保证同组测试数据中的所有道路互不相同，所有测试数据的 $n$ 之和不超过 $10^6$，所有测试数据的 $m$ 之和不超过 $2 \times 10^6$。

输出格式

对于每组测试数据，输出 $n$ 行。在第 $i$ 行中，考虑守卫正站在第 $i$ 个房间的情况。如果此时不存在满足条件的从入口到出口的路径供 Rikka 访问古庙，则在该行输出 $-1$。否则，在该行输出两个由空格分隔的整数，第一个整数是她能获得的最大总价值，第二个整数是她可以选择的不同路径的方案数（以达到该最优结果）。第一个数应按准确值输出，第二个数应对 $(10^9 + 7)$ 取模后输出。

1
4 5
1 2
2 3
3 4
4 2
1 2
1 3
2 4
3 4
1 4
5 3

-1
8 1
-1
-1

提示

翻译由 DeepSeek V4 Pro 完成