BUREAU - Bureaucracy

no tags 

 

Many centuries later lawyers discovered that there were only two types of laws in the kingdom:
² direct law, that states a new norm;
² canceling law, that cancels one of the previous laws.
The law is considered active if and only if there is no active law that cancels it.
You are to write program that ¯nds out which laws are still active.

Long ago, in a kingdom far, far away the king decided to keep a record of all laws of his kingdom. From that moment whenever a new law was passed, a corresponding record was added to the law archive.

Many centuries later lawyers discovered that there were only two types of laws in the kingdom:

  • direct law, that states a new norm;
  • canceling law, that cancels one of the previous laws.

The law is considered active if and only if there is no active law that cancels it.

You are to write program that finds out which laws are still active.

 

Input

The first line of the input contains T, the number of test cases. T test cases follow.

The first line of each test case contains an integer number n (1 <= n <= 100000) - the number of passed laws.

The following n lines describe one law each. Each description has one of the following formats:

  • "declare", meaning that a direct law was passed.
  • "cancel i", where i is the number of law being cancelled by this one.

The laws are numbered from one.

 

Output

For each test case your output must contain a line with the number of active laws. The following line must contain numbers of these laws listed in increasing order.

 

Example

Input:
1
5
declare
cancel 1
declare
cancel 2
cancel 3

Output:
3
1 4 5

hide comments
Nakul Krishna: 2011-12-30 10:35:47

getting runtime error (SIGSEGV)
pls help....

nw TLE :(

and nw WA :(

Last edit: 2012-01-03 15:09:27
sri: 2011-12-06 13:32:27

a law cannot be canceled before declaring it

BOND: 2011-11-28 08:36:09

" in a kingdom far, far away " -- is it taken from movie shrek !!! ??
very nice problem...

Hazem: 2011-11-10 17:15:56

can a law be canceled before actually declaring it

apt-get: 2011-08-05 18:37:05

is the order of laws chronological ? ( can a law be canceled before actually declaring it ? )

Last edit: 2011-08-05 18:40:22
Kashyap Krishnakumar: 2011-07-09 07:29:02

@Fidel: Very nice problem :-) I loved it!

Santiago Palacio: 2011-06-26 20:06:44

Is it possible to declare a law that has not been made? (i mean, that the first law for example is cancel 3)?

S: 2011-04-18 06:03:29

any ambiguous test cases possible?like
4
declare
cancel 1
cancel 1
cancel 3

Marcelo Quiroz Alcocer: 2011-04-16 19:03:03

my code works well tell me the final output is to jump online or not, even as it is t I added long long for support.
sorry for my english

Last edit: 2011-04-17 16:37:14
Fidel Schaposnik: 2011-03-08 16:23:09

@[[soup_boy]]: it would obviously be paradoxical to do so, so the answer is "no"...

Last edit: 2013-02-10 04:24:18

Added by:Fidel Schaposnik
Date:2011-01-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC 2009, NEERC, Northern Subregional Contest