Chaapu and Matisse
All submissions for this problem are available.
This is the story of Chaapu, who is off on a business trip to New York, and takes your advice on how to come up with algorithmic solutions for his day to day problems.
Our brilliant Chaapu has already blazed through the work at the office. An excellent planner, Chaapu had organized his load very effectively, so that he can utilize the extra time to visit some of the tourist attractions in New York.
Being an art lover, his first stop was The Museum of Modern Art (MoMA) (He is more of an abstractionist). He was thrilled as there was a limited edition exhibition containing some of the most beautiful cut-outs by Henri Matisse, known for his unique symbolism and effective color palette with which he made his pieces using only paper and scissors (Hence the name cutouts)
Deeply interested in color theory, Chaapu stood rooted at his spot, as he lay his eyes on The Thousand and One Nights by Matisse. He noticed that there were N distinct colors (Represented by integers ranging from 1 to N. With his knowledge of colors, he knew that M pairs of these colors were "coherent" with each other i.e gelled well with each other. Also, even if two colors A and B are not directly coherent, they can be indirectly coherent if there is a set of colors in the painting A, X1, X2, .... , Xk, B such that all pairs of consecutive colors are coherent with each other.
Chaapu's mind began to work in all directions.
- What would happen to the coherence between color A and color B if the direct coherence (It belongs to the set of M pairs) between color C and D was ignored?
- What would happen to the coherence between color A and color B if a color C was removed?
He turns to your algorithmic ingenuity to answer his queries. There are Q of them.
Note: The queries are not operations, as in they do not remove the color or the relationship from the current data-set.
The first line of the input contains N and M, the number of distinct colors and number of coherent pairs respectively.
The next M lines contain two space separated integers A and B, denoting the two-way coherent relationship between colors A and B.
The next line contains integer Q, denoting the number of queries.
The first integer in rest of the Q lines is either 1 or 2 denoting the type of query in the same order as given above.
If query type is 1, there are four additional integers in the line, namely, A, B, C, D. A and B will be different. C and D will have an existing relationship between them.
If query type is 2, there are three additional integers in the line, namely, A, B, C. A, B and C will be different.
Output "yes" (without quotes) if there would exist a coherent relationship between A and B as per the queries explained above. Otherwise output "no"
- 1 ≤ N ≤ 100000
- 1 ≤ M ≤ 500000
- 1 ≤ Q ≤ 300000
- 1 ≤ A, B, C, D ≤ N
Input: 4 4 1 2 2 3 3 1 4 1 3 1 2 3 1 4 2 2 4 1 2 2 3 1
Output: yes no yes
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.