بيان المسألة

في الولايات المتحدة في JOI، توجد $N$ مدن مرقمة من $1$ إلى $N$، و $M$ طرق مرقمة من $1$ إلى $M$. يربط الطريق $i$ ($1 \le i \le M$) بين المدينة $U_i$ والمدينة $V_i$ في كلا الاتجاهين.

تتكون الولايات المتحدة في JOI من $K$ ولايات مرقمة من $1$ إلى $K$. تنتمي المدينة $j$ ($1 \le j \le N$) إلى الولاية $S_j$. كما تحتوي كل ولاية على مدينة $1$ على الأقل.

يخطط المدير K، وزير الصناعة في الولايات المتحدة في JOI، لإجراء $Q$ صفقات تجارية من الآن فصاعدًا. الصفقة التجارية رقم $k$ ($1 \le k \le Q$) تتمثل في نقل المنتجات المميزة من المدينة $A_k$ إلى المدينة $B_k$ مرورًا ببعض الطرق والمدن. ومع ذلك، تتعاون في هذه الصفقة الولاية $S_{A_k}$ والولاية $S_{B_k}$ فقط (أو الولاية $S_{A_k}$ فقط عندما يكون $S_{A_k} = S_{B_k}$)، وإذا مر المسار عبر أي مدينة لا تنتمي إلى هاتين الولايتين، فستتم سرقة المنتجات المميزة.

يرغب المدير 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$)، يوجد $j$ ($1 \le j \le N$) بحيث يكون $S_j = l$.
• $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$)، اطبع 1 إذا كان من الممكن توصيل المنتجات المميزة في الصفقة التجارية رقم $k$، واطبع 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$ إلى المدينة $3$ بالمرور فقط عبر المدن التي تنتمي إلى الولاية $1$. بما أنه لا يوجد مسار نقل يحقق الشرط، نطبع 0.
• الصفقة التجارية رقم $3$ هي نقل المنتجات المميزة من المدينة $1$ إلى المدينة $4$ بالمرور فقط عبر المدن التي تنتمي إلى الولاية $1$ أو الولاية $2$. النقل عبر المدينة $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$.