Constrained Selection

All submissions for this problem are available.
Given a rooted tree consisting of N nodes rooted at node number 1, and a value val[i] associated with each node i. We need to state if it is possible to select a subset of nodes such that if X is the set of selected nodes and Y is the set of not selected nodes, no two nodes a, b should satisfy any of the following properties: a belongs to X, b belongs to X and val[a]*val[b]%N = 1
 a belongs to Y, b belongs to Y and val[a]*val[b]%N = 1
 a belongs to X, b belongs to X, a is an ancestor of b and gcd(val[a],val[b]) > 1
Report if it is possible to select such a subset of nodes.
Input Format:
First line contains a single integer, the number of test cases T.Inputs for T test cases follow.
First line for each test case contains a single integer, the number of nodes N.
The next line contains N space seperated integers, ith number denoting val[i].
The next N1 lines contain 2 space seperated integers each: x y, denoting that there is an edge between the nodes x and y.
Output Format:
Print T lines, one for each test case.If it is possible to select such a subset of nodes, print "Yes", else print "No" (Without Quotations).
Constraints:
 1<= T <= 200000
 1<= N <= 200000
 Sum of all N over all test cases <= 200000
 1<= val[i] < N
 1<= x, y <= N
 x != y
Sample Input:
27
1 3 6 5 4 3 5
1 2
2 3
2 4
2 5
3 6
4 7
3
1 1 2
1 2
1 3
Sample Output:
NoYes
Author:  gvaibhav21 
Editorial  https://discuss.codechef.com/problems/CONSEL 
Tags  2sat, auxiliarytree, gvaibhav21, inso2018, insomnia18 
Date Added:  21032018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions