Limits
1s, 512 MB

King of Babuland is going through a tough time because of a migrating group of bandits which came to his kingdom. The bandits made the king realize that the people of that country don't get enough light in the night. The bandits took advantage of that matter and looted the houses of the innocent civilians of Babuland.

The king is at a loss about what to do. One day after suffering a lot of days the scientists appointed by the king invented a special lamp which dispersed enough light that emitted the darkness for one house fully. So, the king got $\bf{n}$ Lamps as soon as possible.

But there was a serious issue with the device which was that **if two devices were connected there would be an explosion**. But the issue was solved almost immediately. The scientists just did a pro scientist move and did something which is called *“flipping the parity”*. **If two lamps with the same parity are connected directly there will be a big explosion**. To make it easier to understand the lamps were divided into two classes, **Red** and **Green**.

So, there are $\bf{n}$ lamps for $\bf{n}$ houses which can be deemed **red** or **green**. The lamps are connected through wires that go along the roads that connect one house to another. Every house is connected directly or indirectly. The connection must start from an entrance of the kingdom. There can be multiple entrances. There is always a house at an entrance which is connected to one other house only. The first light must be a red one.

Now the king called the city planners and gave them the task to find out if the whole city can be enlightened using the lamps or not. If yes, the king told specially to see to it that the red light count is maximized while filling the city with lights from the lamps.

You have to help the city planners.

Given $\bf{n}$ and an adjacency matrix of $\bf{n*n}$ denoting the information of the roads, you have to tell if it is possible to enlighten the city and if possible what can be the **number of red lights and green lights where the number of red lights are maximized.**

The first line of input contains a single integer $\bf{n}$ denotes **the number of Houses**.

Then $\bf{n}$ lines follow each containing either $\bf{0}$ or $\bf{1}$. $\bf{A_{ij}}$ means there is a road between $\bf{i^{th}}$ house and $\bf{j^{th}}$ house.

$\bf{1 \le n, A_{ij} \le 10^3}$

Print “**Possible! Possible!**” and the number of red light and green light where count of red light should be maximized if the kingdom can be enlightened with all green and red lamps otherwise “**Pardon Dear Lord! It is not Possible.**”.

Input | Output |
---|---|

7 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 | Possible! Possible! 4 3 |

Input | Output |
---|---|

5 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 | Pardon Dear Lord! It is not Possible. |

**In the First Sample Case**

Here, the house **1**, **4** and **7** has only one house connected to them. So, they are potential starting points as they satisfy the conditions of being entrance of BabuLand.

If we start from **house 4** or **house 7** we can place **4 red** **lamps** and **3 green** **lamps**. But if we start from **house 1** we will get **3 red lamps** and **4 green lamps**. Thus if we need to maximize the count of the **red lamps** then **house 4** or **house 7** should be our starting house.

Be careful about the **newline(‘\n’)** at the end.

Login to submit.

75%
Solution Ratio

SIGMA_77Earliest,

Rakib.4411Fastest, 0.0s

Rakib.4411Lightest, 4.9 MB

Rakib.4411Shortest, 1161B

Toph uses cookies. By continuing you agree to our Cookie Policy.