These are hard times for Dumbledore’s followers in Hogwarts. The Ministry of Magic is interfering at Hogwarts, and assigned Dolores Umbridge for this work. Some students oppose the the Ministry’s rules and have established alliances as the Dumbledore’s Army. Professor Umbridge wants to dissolve this alliances and punish all who break the rules and defy the Ministry, that’s why she assigned to Draco and the Inquisitorial Squad a very special mission: determine which students belongs to the Dumbledore Army. To achieve this mission the Inquisitorial Squad must observe the behaviour of the students and determine if they are allies (support the Ministry) or enemies (belong to the Dumbledore’s Army). The Inquisitorial Squad can mark the relation between two students as friendship or enmity, according to their behaviour and following the next rules: • Two students are allies if their loyalties are the same. • Two students are enemies if they have different loyalties. • A student is by definition ally of himself. • Nobody is an enemy of himself. • Both relations of friendship or enmity are mutual. • “Friends of my friends are my friends too”. If the student x is ally of student y and student y is ally with student z, then x is ally with z too. • “Theenemyofmyenemyismyfriend”. Ifxisaenemyofzandzisanenemyofy,thenxisa friend of y. • “Theenemyofafriendismyenemytoo”. Ifxisafriendofyandyisanenemyofz,thenzis an enemy of x too. Professor Umbridge is not so patient, so she will be asking questions to the Inquisitorial Squad while they do the mission, and they have to answer on the basis of their observations so far. You may assume that the at beginning of the mission don’t exist friendship or enmity relationships between any two students. Input Input contains several test cases. Each test case begins with two integers n and q (1 ≤ n ≤ 10000, 1 ≤ q ≤ 100000), the number of Hogwarts students and the number of operations made by the Inquisitorial Squad. Each of the q following lines contains 3 integers c, x and y (0 ≤ x, y < n), where x and y are the number of the student and c is the code of the operation: • c = 1 means that the Inquisitorial Squad mark the relationship of students x and y as friendship. This relationship will be saved only if it does not contradict with previously detected relationships. • c = 2 means that the Inquisitorial Squad mark the relationship of students x and y as enmity. This relationship will be saved only if it does not contradict with previously detected relationships. • c = 3 means that Umbridge ask the Inquisitorial Squad if students x and y are friends. • c = 4 means that Umbridge ask the Inquisitorial Squad if students x and y are enemies.
2/2 Output For every Umbridge’s question print ‘1’ meaning yes or ‘0’ meaning no. For every time that the In- quisitorial Squad determine a relationship that contradicts previous knowledge print ‘-1’. Relationships that are accord the rules doesn’t gives output. All the integers in the output must be separated by one line break. Sample Input 6 14 112 145 353 445 312 223 113 413 135 220 430 330 315 425 Sample Output 0 0 1 -1 1 0 1 0 1