SOPARADE - Soldiers on Parade

no tags 

Protocol is really weird in Byteland. For instance, it is required that, when presenting arms before an officer, soldiers should stand in a single row (at positions numbered from 1 to n). Soldiers may have one of 4 possible ranks, distinguished by the number of squiggles on the epaulets (between 1 and 4). Soldiers standing beside each other must have a difference in rank of at least two squiggles. Moreover, there are additional sets of rules (different for every province). Each rule states that soldiers standing at some given positions of the row must differ in rank by at least a squiggle.

Starting from the new year onwards, some provinces are changing their set of protocol rules. As the Senior Military Secretary of Protocol, it is your task to approve the new rules. To your surprise, some of the provinces have put forward protocol rules which are quite impossible to fulfill, even if the soldiers were to be specially selected for the purpose of presenting arms. Detect all such offending provinces and on no account approve their laws.


The first line of input contains a single positive integer t<=10 - the number of provinces which are proposing new laws. t sets of rules follow, separated by empty lines.

Each set of rule begins with a line containing two non-negative integers n p (n<=100000, p<=100000) - the number of soldiers arranged and the number of rules proposed in the province, respectively. Each of the next p lines contains a single rule: an integer bi (2<=bi<=n), followed by bi integers a1,a2,...,abi (1<=ak<=n). Such a rule means that soldiers standing at positions a1,a2,...,abi must all be of different rank.


For every set of rules presented at input, output a single line containing the word rejected if no unit of soldiers can be arranged in accordance with protocol, or the word approved in the opposite case.



2 1
2 1 2

5 2
3 1 3 2
4 2 3 4 5


hide comments

Added by:adrian
Time limit:9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:DASM Programming League 2004 (problemset 1)