Rainbow Fish

Ook the Oktopus is bored from sitting in his castle all day long and has recently acquired some rainbow fish to keep as pets. The pet fish come in some apparently random colors of (in no particular order) red, amber, neon pink, dark green, orange and magenta (which is coincidentally a bit difficult to distinguish from neon pink).

Ook has prepared a delightful aquarium for his fishy friends. Each tank can hold an infinite amount of fish, and different tanks can be connected by tubes where fishes can socialize and mix tank water. Tanks are either transparent or colored black (in case the fish want some privacy), while tubes are always transparent, bendy, long enough to connect any two tanks and wide enough to accommodate any number of fish moving in either direction at the same time. Fish can swim infinitely fast, and hence they can create strong currents when they swim in a circle. Ook's fish are overly competitive and love to have fish races, where the fish involved will start from the same tank and swim through a series of tubes such that they end up at the original tank. This could create currents that can tear apart the entire aquarium! So in the end, Ook had no choice but to construct his aquarium such that there is no way the fish can play their games.

Devoid of their fun and entirely harmless racing game, Ook's fish start to get bored. This seems to stem from an unfortunate lack of open, honest communication in the relationship. Ook spends his days agonizing about inter-species speech translation (he needs someone to help him write a program which maps concepts in rainbow fish speech and concepts in Oktopus speech into the same vector space, but that is another problem entirely). Sadly, the fish have taken Ook's embarrassing lack of technical prowess as a sign of Ook's unwillingness to talk things through.

Hence, the fish have decided to spend their days in the aquarium learning magic (the plight of subaquatic beings lacking opposable thumbs!). Coincidentally, all of Ook's rainbow fish have an innate ability to wield magic powers. However, these magical powers need certain environmental factors to surface (that's why the fish didn't find out about their magical powers earlier). The fish discover that the black tanks are best for performing black magic. Each fish has a certain magical power x and a predisposition towards black magic y (where yx). In order for a fish to utilize its magic, the fish needs to be in a connected group of x tanks which have exactly y black tanks. Each fish would like to know whether the current aquarium setup will allow it to practice magic (i.e. the ith fish would like to know if there exists a connected group of xi tanks with exactly yi black tanks), otherwise they will ask another fish to use its magical powers to transport it to a parallel universe with the correct configuration of tanks, instead of fruitlessly searching for the correct group of tanks. The fish would like you to help them write a program to answer each of their questions, because fish have limited memory and would otherwise spend forever swimming around trying to drive the tanks and remembering where the black tanks are.


The first line contains N, the number of tanks. Tanks are numbered from 1 to N.
The next N lines contain either 0 or 1. A 0 on line i means that tank (i-1) is transparent, while a 1 means the tank is black.
The next N-1 lines contain 2 numbers, a and b. This means there is a tube between tanks a and b.
The next line contains a number F, the number of fish.
The next F lines contain 2 numbers, x and y, each representing the magical requirements of a fish.


The output should contain F lines. Each line should be "YES" if that fish can do magic in the aquarium, and "NO" if that fish needs to be transported to an alternate universe in order to practice magic.


For all subtasks, 1 ≤ N ≤ 1000, 1 ≤ F ≤ 1,000,000, 0 ≤ yxN.

Subtask 1 (1%): Every tank is transparent.

Subtask 2 (11%): 1 ≤ N ≤ 400, 1 ≤ F ≤ 10.

Subtask 3 (31%): 1 ≤ N ≤ 400.

Subtask 4 (21%): The tanks form a line.

Subtask 5 (36%): No further constraints.

Sample Input

1 2
1 3
3 4
3 5
1 1
4 2
5 3
3 0
2 0

Sample Output


Fish 1 can choose {3} or {4}.
Fish 2 can choose {1,2,3,4} or {1,3,4,5}.
Fish 3 cannot stay because there are only 2 black tanks.
Fish 4 cannot stay because there is no connected group of 3 transparent tanks.
Fish 5 can choose {1,2}.

Submitting to 'Rainbow Fish'

You're not logged in! Click here to login

Submitting to 'Rainbow Fish'

You're not logged in! Click here to login

Submitting .cpp to 'Rainbow Fish'

You're not logged in! Click here to login

Time Limit: 0.5 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Mock APIO 2015
Editorial: 1

Subtask Score
1 1
2 11
3 31
4 21
5 36
6 0