409635: GYM103648 L Communist Crows

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Communist Crowstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The Council of Communist Crows (CCC) has finally garnered enough support amongst the local murders of crows for them to launch a communist revolution! This will, of course, require a redistribution of wealth, and the CCC wants to organize the redistribution such that each of the $$$N$$$ murders of crows ends up happy, with their requests met, and also such that some murders of crows directly exchange wealth, in order to mend their relationship in the new communist society.

Based on their population and contributions to the CCC, each murder $$$i$$$ demands that $$$d_i$$$ shiny things end up in their possession at the end of the redistribution. Further, each murder $$$i$$$ begins with some amount $$$a_i$$$ of previously amassed shiny things, which will be subject to the redistribution. Then, because of their territory layouts in the local area, only some murders have direct access to trade shiny things with some murders, meaning that the movement of shiny things directed by the Council will need to be strategically orchestrated in order for the murders' demands to be met. They want the redistribution to be efficient as well, such that any two murders have at most one direct transfer of wealth between them. Lastly, the CCC has constructed a list of $$$T$$$ direct wealth transfers between specific murders that it will require in the redistribution, in order to force those murders to interact with one another and amend their friendships.

Help the CCC plan the communist revolution! Given the local murders' starting amounts of shiny things, their respective demands, which murders can directly exchange wealth, and which murders the CCC requires to directly transfer wealth, determine whether the murders' various demands can actually be met!

Input

The first line of input contains a single integer $$$N$$$ $$$(2 \leq N \leq 300)$$$, denoting the number of local murders of crows. The next $$$N$$$ lines each contain two space-separated integers $$$a_i$$$ and $$$d_i$$$ $$$(0 \leq a_i, d_i \leq 10^6)$$$, representing the $$$i^{th}$$$ murder's starting amount of shiny things and demanded amount of shiny things respectively.

The next line of input contains a single integer $$$P$$$ $$$(1 \leq P \leq N-1)$$$, denoting the number of pairs of murders that live close enough together to exchange wealth. $$$P$$$ lines follow, each containing two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq N)$$$, indicating that the $$$i^{th}$$$ and $$$j^{th}$$$ murders can directly exchange wealth.

Lastly, the next line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq P)$$$, denoting the number of direct transfers required by the CCC. $$$T$$$ lines follow, each containing two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq N)$$$, indicating that the $$$i^{th}$$$ murder must transfer at least one shiny thing to the $$$j^{th}$$$ murder (not the other way around) during the redistribution (the $$$i^{th}$$$ and $$$j^{th}$$$ murders are guaranteed to be close enough to exchange wealth).

Output

If the CCC can successfully orchestrate a communist redistribution under the specified demands and constraints, output COMMUNIST REVOLUTION. Otherwise, print NOT GONNA FLY.

ExamplesInput
4
5 2
3 2
1 4
0 1
3
1 3
2 4
1 4
1
1 4
Output
NOT GONNA FLY
Input
4
5 2
3 2
1 4
0 1
3
1 3
2 4
1 4
1
1 3
Output
COMMUNIST REVOLUTION
Note

In the first test case, because at least one shiny thing must be transferred from murder $$$1$$$ to murder $$$4$$$, it is not possible for both the demands of the murder $$$1$$$ and murder $$$3$$$ to be met.

In the second test case, however, a successful redistribution is possible. For example, if murder $$$1$$$ transfers three shiny things to murder $$$3$$$ (satisfying the transfer requirement from $$$1$$$ to $$$3$$$), and murder $$$2$$$ transfers one shiny thing to murder $$$4$$$, then all of the demands will be met.

加入题单

算法标签: