Есептің шарты

JOI Құрама Штаттарында $1$-ден $N$-ге дейін нөмірленген $N$ қала және $1$-ден $M$-ге дейін нөмірленген $M$ жол бар. $i$-ші жол ($1 \le i \le M$) $U_i$ қаласы мен $V_i$ қаласын екі бағытта байланыстырады.

JOI Құрама Штаттары $1$-ден $K$-ға дейін нөмірленген $K$ штаттан тұрады. $j$ қаласы ($1 \le j \le N$) $S_j$ штатына жатады. Сонымен қатар, әрбір штатта кемінде $1$ қала бар.

JOI Құрама Штаттарының өнеркәсіп министрі К директор бұдан былай $Q$ сауда жасауды жоспарлап отыр. $k$-шы сауда ($1 \le k \le Q$) — кейбір жолдар мен қалалар арқылы өтіп, $A_k$ қаласынан $B_k$ қаласына арнайы өнімдерді тасымалдау. Алайда бұл саудаға тек $S_{A_k}$ штаты мен $S_{B_k}$ штаты ғана (немесе $S_{A_k} = S_{B_k}$ болғанда тек $S_{A_k}$ штаты) атсалысады, ал егер маршрут осы штаттарға жатпайтын кез келген қала арқылы өтсе, арнайы өнімдер ұрланады.

К директор арнайы өнімдерді ұрлатпай сауда жасауға болатын тасымалдау маршрутының бар-жоғын анықтағысы келеді. Қалалар мен жолдардың орналасуы, сондай-ақ штаттар мен саудалар туралы ақпарат берілгенде, әрбір сауда үшін арнайы өнімдерді қауіпсіз жеткізуге болатынын анықтайтын программа жазыңыз.

Шектеулер

• $2 \le N \le 400\,000$.
• $1 \le M \le 400\,000$.
• $1 \le K \le N$.
• $1 \le U_i < V_i \le N$ ($1 \le i \le M$).
• $(U_i, V_i) \neq (U_j, V_j)$ ($1 \le i < j \le M$).
• $1 \le S_j \le K$ ($1 \le j \le N$).
• Әрбір $l$ ($1 \le l \le K$) үшін $S_j = l$ болатындай $j$ ($1 \le j \le N$) табылады.
• $1 \le Q \le 400\,000$.
• $1 \le A_k \le N$ ($1 \le k \le Q$).
• $1 \le B_k \le N$ ($1 \le k \le Q$).
• $A_k \neq B_k$ ($1 \le k \le Q$).
• Барлық кіріс мәндері бүтін сандар болып табылады.

Ішкі есептер

1. ($5$ ұпай) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ ұпай) $l$ штатына ($1 \le l \le K$) жататын барлық қалалар тек жолдар және $l$ штатына жататын қалалар арқылы ғана бір-біріне қатынай алады.
3. ($42$ ұпай) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ ұпай) Қосымша шектеулер жоқ.

Кіріс деректер

Кіріс деректер стандартты кірістен келесі форматта беріледі:

N M K
U_1 V_1
U_2 V_2
:
U_M V_M
S_1 S_2 ... S_N
Q
A_1 B_1
A_2 B_2
:
A_Q B_Q

Шығыс деректер

Стандартты шығысқа $Q$ жол шығарыңыз. $k$-шы жолда ($1 \le k \le Q$), егер $k$-шы саудада арнайы өнімдерді жеткізу мүмкін болса 1, ал мүмкін болмаса 0 шығарыңыз.

1-мысал

4 3 2
1 2
2 3
3 4
1 2 1 2
3
1 2
1 3
1 4

1
0
1

• $1$-ші сауда — тек $1$-штатқа немесе $2$-штатқа жататын қалалар арқылы өтіп, $1$-қаладан $2$-қалаға арнайы өнімдерді тасымалдау. $1$-қала → $2$-қала маршрутымен тасымалдау шартты қанағаттандырады, сондықтан 1 шығарылады.
• $2$-ші сауда — тек $1$-штатқа жататын қалалар арқылы өтіп, $1$-қаладан $3$-қалаға арнайы өнімдерді тасымалдау. Шартты қанағаттандыратын тасымалдау маршруты жоқ болғандықтан, 0 шығарылады.
• $3$-ші сауда — тек $1$-штатқа немесе $2$-штатқа жататын қалалар арқылы өтіп, $1$-қаладан $4$-қалаға арнайы өнімдерді тасымалдау. $1$-қала → $2$-қала → $3$-қала → $4$-қала маршрутымен тасымалдау шартты қанағаттандырады, сондықтан 1 шығарылады.

Бұл кіріс мысалы $1, 3, 4$ ішкі есептерінің шектеулерін қанағаттандырады.

2-мысал

4 2 1
1 3
2 4
1 1 1 1
4
1 2
1 3
2 3
2 4

0
1
0
1

Бұл кіріс мысалы $1, 3, 4$ ішкі есептерінің шектеулерін қанағаттандырады.

3-мысал

6 5 3
1 2
3 4
5 6
1 4
3 5
1 1 2 2 3 3
4
1 4
1 5
3 6
4 3

1
0
1
1

Бұл кіріс мысалы барлық ішкі есептердің шектеулерін қанағаттандырады.

4-мысал

8 11 3
4 8
1 8
4 6
3 5
2 4
7 8
6 7
3 4
1 4
2 3
3 8
2 3 1 1 2 1 2 1
10
8 2
8 1
2 7
5 3
5 7
4 8
1 8
6 8
6 5
1 8

1
1
0
1
0
1
1
1
1
1

Бұл кіріс мысалы $1, 3, 4$ ішкі есептерінің шектеулерін қанағаттандырады.