Roadworks#5348
In the Republic of X, a two-party system has existed since ancient times. Each year, citizens with voting rights decide which party they trust more: the Party of Swindlers or the Party of Robbers. During that year, all real power is concentrated in the hands of the chosen party.
Over the past years, a fierce battle has erupted between the parties over the restructuring of the republic's road network to serve their interests. The Party of Swindlers seeks to construct as many state roads as possible to divert more budget money for their "maintenance," while the Party of Robbers tries to convert as many roads as possible into toll roads. All roads in the Republic of X are bidirectional.
It is known that during each year under the Swindlers' rule, they build exactly one new road (which is initially free), and during each year under the Robbers' rule, they impose a toll on one of the currently free roads (after which funds for this road's maintenance are collected from tolls instead of the budget).
The president of the republic, currently lacking real political influence, decided to draw public attention to the road issue. He defined the road network as convenient (for ordinary citizens) if it is possible to travel from any city to any other using only free roads, while also ensuring that the number of free roads (and thus the budget funds for their maintenance, collected through citizens' taxes) is as minimal as possible.
Your task is to write a program that determines whether the road network was convenient at the end of the -th year of the "road war."
The first line contains two integers (1 \leq N \leq 1000), the number of cities in the Republic of X, and (1 \leq M \leq 100000), the duration of the prolonged "road war." Each of the next lines starts with a symbol: if the Swindlers' party was in power that year, or if the Robbers' party was in power, followed by two numbers — the city indices u_i and v_i — representing a pair of cities between which the road became the focus of the respective party's actions (a new road was built if the Swindlers were in power, or an existing road was made toll-based if the Robbers were in power). There may be multiple roads between the same two cities, or even a road from a city to itself.
It is guaranteed that all u_i and v_i are integers from to , and that whenever a toll is imposed between two cities, there was at least one free road between them before that year.
For each year, output a single line: YES if the road network was convenient at the end of that year, and NO otherwise.
Example 1