#CW32. 封锁通路(detour)

封锁通路(detour)

题目描述

小 W 正在检查一张由 nn 个房间和 mm 条单向通道组成的地图。地图是一张有向无环图,入口为房间 11,出口为房间 nn。第 ii 个房间存放一件重量为 wiw_i、价值为 cic_i 的物品。

一条游览路线是从房间 11 到房间 nn 的有向路径。小 W 会取得路径上所有房间的物品。只有物品总重量除以 kk 的余数等于 tt 时,这条路线才合法。

小 Z 会封锁一个房间。对每个 i=1,2,…,ni=1,2,\dots,n,请分别计算房间 ii 被封锁、路线不能经过该房间时:

  • 合法路线能够取得的最大总价值;
  • 达到最大总价值的不同路线数量,对 109+710^9+7 取模。

若不存在合法路线,输出 −1-1。

输入格式

第一行输入一个整数 TT,表示测试数据组数。

每组数据中:

  1. 第一行输入两个整数 n,mn,m;
  2. 接下来 nn 行,第 ii 行输入 wi,ciw_i,c_i;
  3. 接下来 mm 行,每行输入两个整数 u,vu,v,表示一条从 uu 到 vv 的通道;
  4. 最后一行输入两个整数 k,tk,t。

输出格式

对每组数据输出 nn 行。第 ii 行表示房间 ii 被封锁时的答案。

若不存在合法路线,输出 −1-1;否则输出两个整数,依次表示最大总价值和达到该价值的路线数量。路线数量对 109+710^9+7 取模。

样例 1 输入

1
5 6
1 5
1 8
1 8
1 3
1 6
1 2
1 3
2 4
3 4
2 5
4 5
2 0

样例 1 输出

-1
22 1
22 1
-1
-1

样例 1 解释

未封锁时,经过房间 2,42,4 或经过房间 3,43,4 的两条路线均合法,价值均为 2222。封锁房间 22 后只能使用后一条,封锁房间 33 后只能使用前一条。入口、出口或房间 44 被封锁时不存在合法路线。

样例 2 输入

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

样例 2 输出

-1
6 1
6 1
6 2
-1

数据范围

对于所有测试数据:

  • 1≤T≤10001 \le T \le 1000;
  • 2≤n≤1052 \le n \le 10^5,0≤m≤2×1050 \le m \le 2\times 10^5;
  • 1≤wi,ci≤1091 \le w_i,c_i \le 10^9;
  • 1≤u,v≤n1 \le u,v \le n,u≠vu \neq v;
  • 0≤t<k≤1000 \le t < k \le 100;
  • 图中没有重边,且图为有向无环图;
  • 不保证原图存在从房间 11 到房间 nn 的路径;
  • 所有测试数据的 ∑n≤106\sum n \le 10^6,∑m≤2×106\sum m \le 2\times 10^6。
数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 n≤12n \le 12,m≤30m \le 30,k≤6k \le 6
B 15 3∼53\sim 5 n≤100n \le 100,m≤500m \le 500,k≤10k \le 10
C 20 6∼96\sim 9 k=1k=1
D 25 10∼1410\sim 14 n≤2000n \le 2000,m≤5000m \le 5000,k≤20k \le 20,且每条通道均满足 u<vu<v
E 30 15∼2015\sim 20 无额外限制