Under construction

Still being built. Things may change

Crime House (Large)

Time limit5sMemory limit512 MB

Summary
Decide if an enter and leave log with masked identities fits a single door and find the smallest possible number of people left inside.
Level

Medium6 of 10

Topics
Greedy, Simulation, Hash map
Solved
No attempts yet

Problem

While working for the police you found a house where people gather to commit crimes. Everyone calls it Crime House. One day you mounted a camera above the front door and recorded a full day of video.

You do not know how many people were inside when the day began, but every person who passes through the front door shows up on the video. The people who come and go are criminals, so some of them wear masks, and you are not even sure that the front door is the only way in or out.

Sometimes you can work out who was behind a mask. If criminal 5 entered the house, then a masked person left, then criminal 5 entered again, then either the masked person was criminal 5, or Crime House has another exit.

At the end of the day, after the house has closed its doors for the night, you watch the video. Decide whether some scenario fits the video in which the front door is the only entrance and the only exit. If such a scenario exists, find the smallest number of people who could be inside Crime House at the end of the day.

A scenario has to obey these rules.

  • Each person is either inside the house or outside it. The same person is never inside twice at the same time.
  • A record E means a person who was outside entered through the front door. A record L means a person who was inside left through the front door.
  • A record whose id is 0 is a masked person of unknown identity. That person can be someone who appears with a positive id in another record of the video, or someone whose identity never shows up at all.
  • The number of people inside when the day begins, and who they are, is unknown.

Input

The first line of the input gives the number of test cases TT. TT test cases follow. Each test case starts with a line containing a single integer NN, the number of times people pass through the front door of Crime House during the day. NN lines follow, one record per line in chronological order. Each record is a single character, E or L, followed by a space and then an integer id. If the character is E, someone entered Crime House through the front door. If it is L, someone left through the front door. If id is greater than zero, the person with that identifier entered or left. If id is zero, the person who entered or left was wearing a mask and you do not know who it was.

Limits

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤10001 \le N \le 1000
  • 0≤id≤20000 \le \mathrm{id} \le 2000

Output

For each test case, output one line containing "Case #x: y", where xx is the test case number starting from 1. If it is possible that Crime House has no other entrance or exit, yy is the minimum number of people who could be inside Crime House at the end of the day. Otherwise yy is CRIME TIME.

Examples2

  1. Example 1

    Input
    5
3
E 5
L 0
E 5
2
L 1
L 1
4
L 1
E 0
E 0
L 1
7
L 2
E 0
E 1
E 2
E 0
E 3
L 4
13
L 4
L 1
L 2
E 0
L 1
E 0
L 2
E 0
L 2
E 0
E 0
L 1
L 4
    Expected output
    Case #1: 1
Case #2: CRIME TIME
Case #3: 1
Case #4: 4
Case #5: 0

  2. Example 2

    Input
    10
1
E 0
1
L 0
1
E 7
1
L 7
2
E 0
L 0
2
L 0
E 0
2
E 1
E 1
2
L 1
L 1
2
E 1
L 1
2
L 1
E 1
    Expected output
    Case #1: 1
Case #2: 0
Case #3: 1
Case #4: 0
Case #5: 0
Case #6: 1
Case #7: CRIME TIME
Case #8: CRIME TIME
Case #9: 0
Case #10: 1