תיאור הבעיה

בארצות הברית של 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$.