codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

114B.md (2344B)


      1 Source: https://codeforces.com/problemset/problem/114/B
      2 
      3 B. PFAST Inc.
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 When little Petya grew up and entered the university, he started to take part in АСМ contests. Later he realized that he doesn't like how the АСМ contests are organised: the team could only have three members (and he couldn't take all his friends to the competitions and distribute the tasks between the team members efficiently), so he decided to organize his own contests PFAST Inc. — Petr and Friends Are Solving Tasks Corporation. PFAST Inc. rules allow a team to have unlimited number of members.
     22 
     23 To make this format of contests popular he organised his own tournament. To create the team he will prepare for the contest organised by the PFAST Inc. rules, he chose several volunteers (up to 16 people) and decided to compile a team from them. Petya understands perfectly that if a team has two people that don't get on well, then the team will perform poorly. Put together a team with as many players as possible given that all players should get on well with each other.
     24 
     25 Input
     26 
     27 The first line contains two integer numbers *n* (1 ≤ *n* ≤ 16) — the number of volunteers, and *m* (![](https://espresso.codeforces.com/35327467f2c3b20f43402683e6545bccfc361a3b.png)) — the number of pairs that do not get on. Next *n* lines contain the volunteers' names (each name is a non-empty string consisting of no more than 10 uppercase and/or lowercase Latin letters). Next *m* lines contain two names — the names of the volunteers who do not get on. The names in pair are separated with a single space. Each pair of volunteers who do not get on occurs exactly once. The strings are case-sensitive. All *n* names are distinct.
     28 
     29 Output
     30 
     31 The first output line should contain the single number *k* — the number of people in the sought team. Next *k* lines should contain the names of the sought team's participants in the lexicographical order. If there are several variants to solve the problem, print any of them. Petya might not be a member of the sought team.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 3 1  
     39 Petya  
     40 Vasya  
     41 Masha  
     42 Petya Vasya
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 2  
     49 Masha  
     50 Petya
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 3 0  
     57 Pasha  
     58 Lesha  
     59 Vanya
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 3  
     66 Lesha  
     67 Pasha  
     68 Vanya
     69 ```