It’s almost the end of the film! All the heroes and villains are in a Mexican standoff, pointing guns at each other and tensely waiting for the final shoot-out. Huge secrets are being revealed! Alliances are shifting! Who will live and who will die? Nothing is certain.
Every character has a gun and can aim it at one other character. All the characters have perfect aim, so when they fire, the person they’re aiming at certainly dies. Everyone also has superhuman reaction time, so in the instant before they die, they also fire their gun. The next person also squeezes the trigger and then dies, and so on, until it reaches someone who wasn’t aiming at anyone or someone who’s already dead.
Initially, nobody is aiming at anyone. During the standoff, two things can happen:
The input file for each subproblem consists of one single test case.
The first line of the input file contains an integer n specifying the number of characters and an integer q specifying the number of events. The characters in the film are numbered from 1 to n.
Each of the next q lines contains either “1 a b” (1 ≤ a ≤ n, 0 ≤ b ≤ n), which means that character a pointed their gun at character b (or at nobody if b is zero), or “2 a b” (1 ≤ a, b ≤ n), which means that you want to know whether b would die if a would fire.
In the easy subproblem G1 you may assume that n = 3 000 000 and 1 ≤ q ≤ 10 000 000, and also that there will never be a group of characters aiming at each other in a cycle.
In the hard subproblem G2 you may assume that n = 5 000 000 and 1 ≤ q ≤ 40 000 000.
Do not assume anything else about the events. In particular, it’s possible that character a was already aiming at character b when you process an event “1 a b”. In that case nothing changes. And in the hard subproblem, if a revealed secret is particularly shocking, a character could even point the gun at themselves.
Because g1.in and g2.in are about 700 MB in total, you cannot download them directly. Instead, we have provided small Python 2 programs g1gen.py and g2gen.py that will generate g1.in and g2.in when executed. Each generator should take under 8 minutes to run on average hardware. We recommend running them early – for example, starting them as you start working on your solution for this problem.
For each question, answer 0 if the character would survive and 1 if the character would die. Concatenate the answers into one long binary number, so that the last (least significant) digit is the answer to the last question. Convert this number to decimal and print it modulo 109 + 9.
Input:
3 12
2 1 2
1 1 2
1 2 3
2 1 3
2 3 1
2 2 2
1 3 1
2 3 3
1 1 0
2 3 3
1 3 3
2 3 3Output:
37