No tags yet

No tag edit access

Time limit per test: 1 second(s)

Memory limit: 262144 kilobytes

Memory limit: 262144 kilobytes

input: standard

output: standard

output: standard

Hurry! Two well-known software companies are recruiting programmers. Initially the total number of unemployed programmers is

Furthermore, there are some pairs of friends among the programmers. Of course, a programmer may have several friends. Friendship is a symmetrical relationship, so if

All such pairs are known to the companies, and the companies follow the rule: a new programmer hired by a company must have at least one friend among the programmers already working in this company. The only exception is a programmer that a company starts with, he can be chosen arbitrarily. It may happen that after a number of turns a company can not longer hire anyone else according to the rule. In this case it stops hiring, while the other company can continue.

As usual, not all the programmers are created equal. There are three geniuses among them, and each company wants to hire as many geniuses as possible. Note that each company always can guarantee one genius to itself starting with a genius. So the question is, which company will hire two geniuses, if they both use optimal strategies.

Note that both companies have the full information during the hiring: friendship relations, who are geniuses and which programmers were hired by each company in each turn.

sample input | sample output |

4 3 1 4 2 4 3 4 | 1 |

sample input | sample output |

6 6 1 4 1 5 2 5 2 6 3 6 3 4 | 2 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2020 15:26:11 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|