Colors
시간 제한3초메모리 제한512 MB
연결된 그래프에서 간선을 따라 a[u]=min(a[u],a[v]) 연산을 반복해 초기 색 a를 목표 색 b로 바꿀 수 있는지 판정한다.
문제
Consider a connected undirected graph with N nodes and M edges. Initially every node u has a color a[u], encoded by an integer between 1 and N. You can repeatedly modify node colors by assigning a[u] = min(a[u], a[v]), where u and v are connected by an edge.
Given a destination coloring b[1] ... b[N], determine whether you can transform a into b.
입력
There are several test cases per input file and you should answer each of them separately.
The first line contains the number of test cases. Each test case is structured as
N M
a[1] a[2] ... a[N]
b[1] b[2] ... b[N]
u1 v1
u2 v2
...
uM vM
출력
For every test case you should print, on a separate line, 1 if a can be transformed into b using the above-mentioned operation and 0 otherwise.
제한
- For all test cases, N ≤ 150,000 and M ≤ 200,000.
- For every input file, the sum of all N ≤ 300,000 and the sum of all M ≤ 400,000.
- 1 ≤ a[i], b[i] ≤ N for all 1 ≤ i ≤ N.