คำอธิบายโจทย์

ในสหรัฐ 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$)
• ค่าที่รับเข้ามาทั้งหมดเป็นจำนวนเต็ม

งานย่อย (Subtasks)

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$