Students and their arrangements <CAST>
Practice
3 (4 votes)
Data structures
Disjoint set
Medium
Queue
Problem
77% Success 1804 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

There is a long line of students in the mess. Each student has a different roll number. Whenever a student will come in the mess, he will search for his friend from the end of the line. As soon as he finds a friend, he stands behind him else at the end of the line. You are the mess manager. At any moment you can ask the student, who is standing in front of the queue, to come and take the food and go out of the mess.

There are N operations of one of the following types:

  • \(E\; x\): A student whose roll number is x \((1 \le x \le 10^5)\) will stand in line according to the method mentioned above.
  • D: You will ask the student, who is standing in front of the line, to come and take the food and go out of the mess. For each of the \(2^{nd}\) type of query, print the roll number of the student, who is standing in front of the line, to come and take the food and go out of the mess.

Note: Friendship is associative i.e. if a is a friend of b and b is a friend of c, then a is a friend of c.

Input format

  • The first line contains two space-separated integers, N and M \((1 \le N \le 10^5, 0 \le M \le 10^5)\), denoting the number of queries and number of friendships respectively.
  • Next M lines contain two space separated integers each, a and b \((1 \le a, b \le 10^5)\), denoting that a is a friend of b.
  • Next N lines contain one of the two types of queries.

Output format

For each of the \(second\) type of query, print the roll number of the student, who is standing in front of the line, to come and take the food and go out of the mess.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
5 votes
Tags:
Data StructuresDisjoint Data StructuresBasics of Disjoint Data Structures
Points:30
12 votes
Tags:
Arrays and StringsData StructuresDisjoint Data StructuresDisjoint SetDisjoint setGraphsMedium
Points:30
10 votes
Tags:
ApprovedData StructuresDisjoint setMedium