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.
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.
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
Login to unlock the editorial
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