Students and their arrangements <CAST>

★★★★★

4 votes

Data Structures, Disjoint set, Medium, Queue

Details

Submissions

Discussion

Editorial

Problem

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.

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

After first operation, student with roll number 1, will stand in the front of the queue as the queue is empty initially.

$Q = 1$

After second operation, student with roll number 3, will stand behind the first student as there is no other member of the same in the queue.

$Q = 1$ <- 3

After third operation, student with roll number 2, will stand behind his friend (i.e. 1) in the queue.

$Q = 1$ <- 2 <- 3

After fourth operation, the student with roll number 1 in the front will come and take the food and go out of the mess.

$Q = 2$ <- 3

After fifth operation, the student with roll number 2 in the front will come and take the food and go out of the mess.

$Q = 3$

After sixth operation, the student with roll number 3 in the front will come and take the food and go out of the mess.