Description

In this round of interstellar war, we have established $n$ bases in the universe, connected by $m$ directed wormholes. We group all wormholes whose destination is base $u$ as base $u$’s wormholes.

Amid fierce warfare, these wormholes are unlikely to last long, and enemy strikes may come at any time. The effective strikes can be divided into two types:

1. The enemy destroys a wormhole. This makes it impossible to directly travel between its two connected bases via this wormhole, but such a strike cannot destroy the two bases it connects.
2. The enemy destroys a base. Since the key technology of a wormhole is concentrated at its exit, this causes all wormholes of that base that have not yet been destroyed to be destroyed together. Wormholes departing from this base, however, will not be destroyed.

Note: Destruction only makes wormholes unusable and does not erase their existence.

To resist the enemy and maintain links between units and bases, we developed two special forces to repair wormholes:

• Type A special forces can repair a specific wormhole.
• Type B special forces can repair all damaged wormholes of a single base.

Given the nature of enemy strikes, we do not stockpile too many strategic supplies at bases. Therefore, as long as any one wormhole of a base is repaired and usable, that base is considered usable.

We have mastered a stringent spatial property that allows our warships to instantaneously jump along wormholes into enemy territory for precise strikes.

To seize the best timing for a counteroffensive, the command must track all changes on the battlefield. The commander believes:

• If, starting from any of our bases, by choosing an appropriate route, one can shuttle through wormholes infinitely many times (the same base or wormhole may be visited multiple times), then this base can “launch a counterattack”.
• To keep the shuttling process continuous and minimize mass–energy loss when switching wormholes at a base, a base can achieve “continuous traversal” if and only if exactly one wormhole departing from that base is usable.
• If all our bases can both “launch a counterattack” and achieve “continuous traversal”, then this moment is an excellent “counteroffensive” moment.

You are ordered to promptly report, based on real-time battlefield information, whether a “counteroffensive” can be carried out at the current moment.

Input Format

The first line contains two positive integers $n, m$.

The next $m$ lines each contain two integers $u, v$, representing a directed wormhole from base $u$ to base $v$. It is guaranteed that $u \ne v$, and there are no duplicate wormholes. Initially, all wormholes and bases are intact.

The next line contains a positive integer $q$ denoting the number of queries.

The following $q$ lines each describe a query or operation. First read an integer $t$ indicating the instruction type:

• If $t = 1$, the next two integers $u, v$ indicate the enemy destroyed the wormhole from base $u$ to base $v$. It is guaranteed that this wormhole exists and has not been destroyed.
• If $t = 2$, the next integer $u$ indicates the enemy destroyed base $u$. If all wormholes of this base have already been destroyed, then this strike has no effect.
• If $t = 3$, the next two integers $u, v$ indicate we repaired the wormhole from base $u$ to base $v$. It is guaranteed that this wormhole exists and has been destroyed.
• If $t = 4$, the next integer $u$ indicates we repaired base $u$. If this base has no destroyed wormholes, then this repair has no effect.

After each instruction is executed, determine whether a counteroffensive can be carried out. Output YES if it can, otherwise output NO.

Output Format

Output exactly $q$ lines. For each instruction, output whether a counteroffensive can be carried out after the instruction is executed.

3 6
2 3
2 1
1 2
1 3
3 1
3 2
11
1 3 2
1 2 3
1 1 3
1 1 2
3 1 3
3 3 2
2 3
1 3 1
3 1 3
4 2
1 3 2

NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO

Hint

【Sample Explanation #1】

You can refer to the following image for the wormhole status. In the figure, an edge denotes a wormhole that exists and has not been destroyed:

【Sample #2】

See galaxy/galaxy2.in and galaxy/galaxy2.ans in the attachment.

【Sample #3】

See galaxy/galaxy3.in and galaxy/galaxy3.ans in the attachment.

【Sample #4】

See galaxy/galaxy4.in and galaxy/galaxy4.ans in the attachment.

Constraints

For all testdata, it is guaranteed that $1 \le n \le 5 \times {10}^5$, $1 \le m \le 5 \times {10}^5$, $1 \le q \le 5 \times {10}^5$.

Translated by ChatGPT 5