Problem B. Professor Q\’s Software
最后更新于:2022-04-02 01:14:57
# Problem B. Professor Q's Software
### Source
- [hihoCoder](http://hihocoder.com/contest/mstest2015april/problem/2)
### Problem
鏃堕棿闄愬埗:10000ms
鍗曠偣鏃堕檺:1000ms
鍐呭瓨闄愬埗:256MB
### 鎻忚堪
Professor Q develops a new software. The software consists of N modules whichare numbered from 1 to N. The i-th module will be started up by signal Si. Ifsignal Si is generated multiple times, the i-th module will also be startedmultiple times. Two different modules may be started up by the same signal.During its lifecircle, the i-th module will generate Ki signals: E1, E2, ...,EKi. These signals may start up other modules and so on. Fortunately thesoftware is so carefully designed that **there is no loop in the startingchain of modules**, which means eventually all the modules will be stoped.Professor Q generates some initial signals and want to know how many timeseach module is started.
![d](image/562b1c8047ba6.png)
### 杈撳叆
The first line contains an integer T, the number of test cases. T test casesfollows.
For each test case, the first line contains contains two numbers N and M,indicating the number of modules and number of signals that Professor Qgenerates initially.
The second line contains M integers, indicating the signals that Professor Qgenerates initially.
Line 3~N + 2, each line describes an module, following the format S, K, E1,E2, ... , EK. S represents the signal that start up this module. K representsthe total amount of signals that are generated during the lifecircle of thismodule. And E1 ... EK are these signals.
For 20% data, all N, M <= 10For 40% data, all N, M <= 103For 100% data, all 1 <= T <= 5, N, M <= 105, 0 <= K <= 3, 0<= S, E <= 105.
**Hint: HUGE input in this problem. Fast IO such as scanf and BufferedReader are recommended.**
### 杈撳嚭
For each test case, output a line with N numbers Ans1, Ans2, ... , AnsN. Ansiis the number of times that the i-th module is started. In case the answersmay be too large, output the answers modulo 142857 (the remainder of divisionby 142857).
鏍蜂緥杈撳叆
~~~
3
3 2
123 256
123 2 456 256
456 3 666 111 256
256 1 90
3 1
100
100 2 200 200
200 1 300
200 0
5 1
1
1 2 2 3
2 2 3 4
3 2 4 5
4 2 5 6
5 2 6 7
~~~
鏍蜂緥杈撳嚭
~~~
1 1 3
1 2 2
1 1 2 3 5
~~~
';