All Tracks Problem

Leaf Village and Democracy
Tag(s):

Hard

Problem
Editorial
Analytics

After his rigorous training with Jiraiya, Naruto came back to the Leaf Village and decided to visit the Zoo of summoning animals.

enter image description here

There are $$N$$ summoning animals numbered from $$1$$ to $$N$$ in the Zoo, all located currently in one common territory. For some reason, recently the summoning animals started fighting with each other and they are making a massive damage. Since the Hokage of the Leaf Village is a democracy fanatic, she decided that all the visitors of the Zoo should decide how to separate the summoning animals into distinct territories, so hopefully they will stop fighting.

The visitors are sending their requests. The total number of requests is denoted by $$Q$$.

Each request is in one of the following forms:

  1. $$SEPARATE(T_1, T_2, \ldots, T_K)$$ - a visitor making this request wants to separate summoning animals into $$K$$ territories, where $$T_i$$ is a list of summoning animals forming the $$i^{th}$$ territory.

  2. $$CANCEL(T_1, T_2, \ldots, T_K)$$ - a visitor making this request wants to cancel a single request of separation the summoning animals into $$K$$ territories $$T_1, T_2, \ldots, T_K$$ described as in the separate request. The cancel request cancels exactly one separation request into this territories, which were requested before and not yet canceled. If there is no such separation request to cancel then nothing happens.

  3. $$ASK()$$ - a visitor making this request wants to know how the Zoo will group all the summoning animals into territories based on all not canceled requests made so far. The Zoo is using the following rule to do that:

    Any two summoning animals cannot be assigned to the same territory if there is at least one present request of a visitor who wants them to be into separated territories. Moreover, the Zoo wants to minimize the number of total territories.

The task in this problem is to handle all $$Q$$ requests made by the visitors.

Constraints:

$$1 \leq N \leq 2000$$
$$1 \leq Q \leq 2000$$
$$1 \leq K \leq N$$

Input format:

In the first line there are two space separated integers $$N$$ and $$Q$$, denoting respectively the number of summoning animals in the Zoo and the number of requests to handle. Description of $$Q$$ requests follow. Each of them is given in one of the $$3$$ below formats:

  1. If it starts with a line $$\texttt{SEPARATE K}$$, it denotes a separate request into $$K$$ territories. Each such request is followed by exactly $$K$$ lines. In the $$i^{th}$$ of them there is a single integer $$M$$ followed by a list of space separated integers $$e_{i_1}, e_{i_2}, …, e_{i_M}$$ denoting the summoning animals assigned to the $$i^{th}$$ territory by this request. In all these $$K$$ lines, all integers denoting summoning animals are distinct and there are exactly $$N$$ of them.

  2. If it starts with a line $$\texttt{CANCEL K}$$, it denotes a cancel request into $$K$$ territories. Each such request is followed by exactly $$K$$ lines. In the $$i^{th}$$ of them there is a single integer $$M$$ followed by a list of space separated integers $$e_{i_1}, e_{i_2}, …, e_{i_M}$$ denoting the summoning animals assigned to the $$i^{th}$$ territory in this request. In all these $$K$$ lines, all integers denoting summoning animals are distinct and there are exactly $$N$$ of them.

  3. If it contains a single word $$ASK$$, it denotes an ask request.

Output format:

For each ask request, output the answer to this request in the following format. In the first line print integer $$K$$ denoting the number of territories that the Zoo decided to use. Then, output exactly $$K$$ lines denoting separation of the summoning animals into these territories. In the $$i^{th}$$ of them an increasing list of $$M$$ space separated integers $$e_{i_1} < e_{i_2} < … < e_{i_M}$$ denoting the numbers of summoning animals assigned to the $$i^{th}$$ territory by the Zoo. The $$i^{th}$$ of these territories have to contain the summoning animal denoted by the smallest integer which is not yet assigned to any previously printed territory for this request. For more details please refer to the sample.

SAMPLE INPUT
4 5
SEPARATE 2
2 1 2
2 3 4
SEPARATE 2
1 4
3 3 1 2
ASK
CANCEL 2
2 3 4
2 2 1
ASK
SAMPLE OUTPUT
3
1 2 
3 
4 
2
1 2 3 
4 
Explanation

In the sample we have $$4$$ summoning animals denoted by the integers $$1, 2, 3, 4$$ and $$5$$ requests incoming from the visitors.

In the first request, a visitor wants to put summoning animals $$1$$ and $$2$$ into one territory and summoning animals $$3$$ and $$4$$ into the other one.

Then, in the second request, another visitor wants to put summoning animal $$4$$ in a separated territory and all other summoning animals into the other territory.

After that, the third visitor wants to know how the Zoo is going to place the summoning animals into territories based on all previously made requests. From the second request, the Zoo knows that summoning animal $$4$$ cannot be with any other summoning animal into one territory and from the first request it is clear that summoning animal $$3$$ has to be separated from summoning animals $$1$$ and $$2$$. Thus the Zoo will create $$3$$ territories and will put summoning animals $$1$$ and $$2$$ into the first one, because summoning animal $$1$$ is the smallest not yet assigned to a territory and there are no restrictions by the visitors for putting summoning animal $$2$$ together with $$1$$. In the second territory only summoning animal $$3$$ will be put, because it cannot be together with the summoning animal $$4$$ and it is denoted by a smaller integer. In the last territory the summoning animal $$4$$ will be placed.

In the fourth request, a visitor wants to cancel a previous request which is actually the same as the first request.

The last visitor wants to know how the Zoo is going to place the summoning animals into territories. After the cancelation, the only not canceled request is the second request and the Zoo will assign summoning animals to new territories exactly in the same way as a visitor who made the second request wants them to be placed. Notice that summoning animals in each territory formed by the Zoo provided for each ask request are given are given in the ascending order of their numbers.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications