We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Zurikela's Graph

Zurikela's Graph

Problem
Submissions
Leaderboard
Discussions
Editorial

Zurikela is creating a graph with a special graph maker. At the begining, it is empty and has no nodes or edges. He can perform types of operations:

  1. : Create a set of new nodes and name it -.
  2. : Create edges between nodes of - and -.
  3. : Create a set composed of nodes from - and its directly and indirectly connected nodes, called -. Note that each node can only exist in one set, so other sets become empty.

The first 's name will be -. In first and third operation is referring to the index of new set:

K = [index of last created set] + 1

Create the graph by completing the operations specified during input. Then calculate the maximum number of independent nodes (i.e.:how many nodes in the final graph which don't have direct edge between them).

Input Format

The first line contains .
The subsequent lines each contain an operation to be performed.

Constraints
.
For the first operation, .
For the second operation, and all s are distinct.
For the second and third operation, it's guaranteed that - and - exist.

Output Format

Print maximum number of independent nodes in the final graph (i.e.: nodes which have no direct connection to one another).

Sample Input

8
A 1
A 2
B 1 2
C 1
A 2
A 3
B 3 4
B 4 5

Sample Output

5

Explanation

There are operations.

After first operation:

After second operation:

After third operation:

After fourth operation:

After fifth and sixth operation and :

After seventh operation:

After eigth operation:

There are independent nodes in - and independent nodes in -, so we print their sum () as our answer.

Author

nikasvanidze

Difficulty

Hard

Max Score

80

Submitted By

360

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature