Задача K. Свързани, несвързани
---
N-те населени места на район, номерирани от 1 до N (N ≤ 1000), са свързани с пътища. След като падна сняг, останали проходими само M пътни отсечки, всяка от които свързва две различни населени места. Изнервени граждани, които пътуват, атакуват телефон 112 с въпроси "Може ли да стигнем от X до Y?" Почистващите служби успяват от време-навреме да почистят някоя от пътните отсечки и съобщават на 112: "Пътната отсечка от U до V вече е проходима." Граждани, които са се доверили на информацията и са тръгнали на път, обаче, също се обаждат на телефон 112 за да поискат помощ с оплакването "Пътната отсечка от U до V отново е затрупана". Напишете програма, която да помага на операторите на телeфон 112 да отговарят бързо на въпросите на гражданите за актуалното състояние на пътищата.

Вход
---
На първия ред на стандартния вход ще бъде зададен броят на тестовете. Всеки тест започва с ред с числата N и M. На всеки от следващите M реда има по два номера на град, свързани с проходима пътна отсечка. Следват ред с броя Q на обажданията – както от граждани, така и от пътните служби и Q реда със съдържанието на обажданията – вид на обаждането и двата номера на населените места за които се отнася съответното обаждане. Ако обаждането е въпрос на гражданин – кодът е 1, ако е съобщение от пътните служби – кодът е 2, а ако е информация от зъкъсал на пътя гражданин – кодът е 3.

Изход
---
За всеки тестов пример програмата трябва да изведе иа стандартния изход битов низ с толкова знака, колкото са въпросите на граждани за проходимост на пътната мрежа (заявки с код 1), като знак 0 в низа означава, че отговорът на поредния въпрос е "Не", а знак 1 – "Да".

Ограничения
2 ≤ N ≤ 1000; 
1 ≤ Q ≤ 100000

Пример вход
---
1
9 8
1 2
3 4
5 6
7 8
9 5
7 2
8 2
6 9
8
1 1 8
1 6 2
2 7 1
1 4 7
2 2 3
1 4 7
3 3 4
1 4 7

Примерен изход
---
10010