Tortillas are one of the most characteristic elements of Mexican cuisine. Made with wheat or corn flour, they are used in the preparation of various delicious foods, such as tacos, burritos, and quesadillas. The manager of a famous supermarket in Mexico City went crazy and decided to hold a mega promotion on different types of flour, which attracted many customers to his establishment.
The supermarket has the capacity for $$$k$$$ checkout queues. After finishing their shopping, a customer goes to one of these queues to make the payment. Since people are very stubborn, they never switch queues once they have entered one, even if it's taking too long to move.
A customer becomes sad if, while waiting in a queue, they observe someone entering and leaving another queue.
Considering that $$$n$$$ people are in the supermarket, numbered from 1 to $$$n$$$, you receive a list of $$$2n$$$ events in chronological order indicating the entry or exit of a customer from a queue. Determine which customers will be sad.
The first line of the input contains two integers $$$n$$$ and $$$k$$$, representing the number of people and the number of queues in the supermarket, respectively, such that $$$1 \leq n, k \leq 10^5$$$.
Each of the following $$$2n$$$ lines represents one of the two types of events. For an entry event, the line starts with the number 1, followed by the integers $$$p_i$$$ and $$$f_i$$$, indicating that person $$$p_i$$$ entered queue $$$f_i$$$. For an exit event, the line starts with the number 2, followed by the integer $$$f_i$$$, indicating that the first person in queue $$$f_i$$$ has left. For both cases, the following conditions hold: $$$1 \leq p_i \leq n$$$ and $$$1 \leq f_i \leq k$$$.
Print a line containing an integer $$$m$$$, representing the number of sad people. Then, print another line with $$$m$$$ integers in ascending order, indicating the people who are sad.
4 3 1 1 1 1 2 2 1 3 3 2 2 1 4 1 2 1 2 1 2 3
2 1 3
| 2023 USP Try-outs |
|---|
| Закончено |
